Final answer:
To prove that a^pq ≡ a mod pq for different primes p, q, we use Fermat's Little Theorem and the Chinese Remainder Theorem. By showing that both exponents p and q align with Fermat's Little Theorem and combining this with the Chinese Remainder Theorem, we can deduce the required congruence relationship.
Step-by-step explanation:
The question relates to number theory and Congruence relations in modular arithmetic. Given that p and q are different primes, and it is known that ap ≡ a mod q and aq ≡ a mod p, we need to prove that apq ≡ a mod pq.
Firstly, since ap ≡ a mod q, we apply Fermat's Little Theorem, which tells us that if q is a prime and a is not divisible by q, then aq-1 ≡ 1 mod q. Raising a to the pth power does not change this relationship, therefore ap(q-1) ≡ 1 mod q.
Similarly, from the congruence aq ≡ a mod p, and knowing that p is a prime, we deduce by Fermat's Little Theorem that ap-1 ≡ 1 mod p. Thus, aq(p-1) ≡ 1 mod p. Next, we look at the exponents and realize that both are divisible by p-1 and q-1, hence we have a(p-1)(q-1) ≡ 1 mod p and a(p-1)(q-1) ≡ 1 mod q.
By the Chinese Remainder Theorem, these two congruences lead us to a(p-1)(q-1) ≡ 1 mod pq. Finally, by multiplying both sides of the congruence a(p-1)(q-1) ≡ 1 mod pq by a, we end up with apq ≡ a mod pq, which concludes the proof.