# Thread: Two Not So Quick Questions

1. ## Two Not So Quick Questions

I've been wondering if there are proofs for these two questions... Searching has given me nothing. These aren't new results so they SHOULD be out there, but I can't find them.

1. Let p and q be distinct primes. Prove that, for any $a \in \mathbb{Z}$

$a^{pq} \equiv a^p + a^q (mod \ pq)$

2. Let $a < m$ be two positive integers. Prove that a and m are relatively prime if and only if there is some power of a which is an inverse of a modulo m.

2. Originally Posted by Aryth
I've been wondering if there are proofs for these two questions... Searching has given me nothing. These aren't new results so they SHOULD be out there, but I can't find them.

1. Let p and q be distinct primes. Prove that, for any $a \in \mathbb{Z}$

$a^{pq} \equiv a^p + a^q (mod \ pq)$
this is false! check the question again!

3. Originally Posted by Aryth

2. Let $a < m$ be two positive integers. Prove that a and m are relatively prime if and only if there is some power of a which is an inverse of a modulo m.
the "if" part: if $a^k \equiv a^{-1} \mod m,$ then $a^{k+1} \equiv 1 \mod m.$ now it's clear that $a,m$ cannot have any common divisor greater than 1.

for the "only if" part use this fact that if $\gcd(a,m)=1,$ then $a^{\varphi (m)} \equiv 1 \mod m$ and thus $a^{\varphi(m)-1} \equiv a^{-1} \mod m.$

4. Originally Posted by NonCommAlg
this is false! check the question again!
You're right... I missed a part:

$a^{pq} + a \equiv a^p + a^q (mod \ pq)$

5. Originally Posted by Aryth
You're right... I missed a part:

$a^{pq} + a \equiv a^p + a^q (mod \ pq)$
since $x-y \mid x^n - y^n,$ for any positive integer $n,$ we have $q \mid a^q - a \mid a^{pq} - a^p$ and $p \mid a^p - a \mid a^{pq}-a^q.$ thus $q \mid a^{pq} - a^p$ and $p \mid a^{pq} - a^q.$ thus:

$q \mid a^{pq}-a^p - (a^q - a)$ and $p \mid a^{pq}-a^q - (a^p -a).$ but $a^{pq}-a^p - (a^q - a)= a^{pq}-a^q - (a^p -a).$ thus: $pq \mid a^{pq}-a^p - a^q + a,$ and we're done.

6. Thanks for the help. I really appreciate it.