Modular Arithmatic

Problem Statement:

Let p and q are prime. x be an integer such that
x mod p = 1 and
x mod q = 1

Prove that, x mod pq =1

Solution:

An Observation: The least common multiple of two integers divide all the common multiples of those two integers. This observation can also be proved algebraically. The algebraic proof is not mentioned here.

Now,
x mod p = 1 means, p divides x-1
x mod q = 1 means, q divides x-1

That means x-1 is a common multiple of p and q.

pq is also a common multiple of p and q.

Let us denote the LCM of p and q by LCM(p,q) and GCD of p and q by GCD(p,q).

We know that the LCM of any two integers is obtained by dividing the the product of the two integers by their GCD. That is:  LCM(p,q) = pq/GCD(p,q)

As both p and q are prime, LCM(p,q) = pq

So, from the first statement(Observation) of this solution, we can write that pq divides x - 1

That means x mod pq =1 ( Proved )


Note: I am happy if it helps.