Question 1208759
.
Find the smallest integer which will divide over 45, 72, and 999 leaving remainder as 5, 2, and 9.
~~~~~~~~~~~~~~~~~~~~



Such an integer number does not exist.


Below I will prove it mathematically.


<pre>
Let assume that some integer x satisfies these congruences

    x = 5  (mod 45)     (1)

    x = 2  (mod 72)     (2)

    x = 9  (mod 999)    (3)


Notice that 999 = 9*111,  72 = 8*9.


Congruence (3) tells us that the number  x-9  is divisible by 999.

Hence,  x-9  is divisible by 9, too.


Next, congruence (2) tells us that the number  x-2  is divisible by 72.

Hence,  x-2  is divisible by 9, too.


It is just a contradiction, because the numbers  x-2  and  x-9  can not be divisible 
by 9 simultaneously - otherwise, their difference  (x-2) - (x-9) = 7 would be divisible by 9,
which is not the case.


This contradiction proves  that the system of congruences (1), (2), (3) has no solutions in integer numbers.


In this proof, I used congruences (2) and (3).

But for proving this statement, I could equally use any two congruences of these three given congruences.
</pre>

Solved, with the proof and explanations.


So, this problem is a trap, in some sense.



**********************************************************


        &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;The meaning of this problem is to teach a reader

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(a) &nbsp;to recognize such traps 

          &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;and &nbsp;(b) &nbsp;to prove that the problem is a trap.


**********************************************************