Question 1208759: Find the smallest integer which will divide over 45, 72, and 999 leaving remainder as 5, 2, and 9.
Found 2 solutions by math_tutor2020, ikleyn:
Answer by math_tutor2020(3817)   (Show Source):
You can put this solution on YOUR website!
The goal is to solve this system of congruences
x = 5 (mod 45)
x = 2 (mod 72)
x = 9 (mod 999)
Recall that if a = b (mod n) then a-b = nk for some integer k.
Rearranging things gives a = nk + b.
Use this idea to transform the first two equations into x = 45k+5 and x = 72m+2. We cannot re-use k.
Both equations involve x, so equate the right hand sides and we get,
72m+2 = 45k+5
72m-45k = 5-2
9(8m-5k) = 3
9(integer-integer) = 3
9*(integer) = 3
integer = 3/9
integer = 1/3
which is a contradiction. The value 1/3 = 0.33333... is not in the set of integers.
Therefore the first two equations of the original system do not have a solution.
Overall the entire system doesn't have a solution either.
--------------------
I used a Python script to check integers from x = 1 to x = 10,000,000 and couldn't find any solutions.
This numeric approach of course doesn't prove there aren't any solutions, since there are infinitely many integers to check, but it's useful to get partial backup confirmation.
A spreadsheet is another alternative verification route.
You may be asking yourself "Can we use Chinese Remainder Theorem?"
The answer would be "No because the mod values 45, 72, and 999 are not pairwise coprime."
------------------------------------------------------------
------------------------------------------------------------
Answer: No solutions
Answer by ikleyn(52781)  (Show Source):
You can put this solution on YOUR website! .
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.
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.
Solved, with the proof and explanations.
So, this problem is a trap, in some sense.
**********************************************************
The meaning of this problem is to teach a reader
(a) to recognize such traps
and (b) to prove that the problem is a trap.
**********************************************************
|
|
|
