Chinese Remainder Theorem

Question

Prove that there does not exist an integer c and a natural number x ≥ 2 such that c ≡ 2 (mod x) and c ≡ 3 (mod x^3 ).

 

By the Chinese Remainder Theorem, the system is solvable if gcd(x,x^3) | 2 -3  which implies x | 1. How do i continue from here?

Answer 1

The Chinese Remainder Theorem cannot be used if any modulus shares a factor with the others. In this case x³ and x have factor x in common.

c=ax+2 is the same as c≡2(mod x),

c=bx³+3 is the same as c≡3(mod x³), where a and b are natural numbers.

Therefore:

ax+2=bx³+3=x(bx²+3/x).

Divide through by x:

a+2/x=bx²+3/x.

If x=1 then a+2=b+3 and b=a-1, but we are only interested in x≥2;

If x=2 then a+1=4b+3/2, but we have an integer on the left-hand side and a mixed number on the right-hand side. Equality is not possible.

If x=3 then a+2/3=9b+1. Again, equality is not possible because RHS is an integer but LHS is a mixed number.

For x>3, a and bx² are integers, both LHS and RHS are mixed numbers, but 2/x cannot be equal to 3/x for x>1. This implies that there can be no integer c for which c≡2(mod x) and c≡3(mod x³).