# Why does $y^{pq} ≡ y$[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? $p, q$ prime.

Why does $y^{pq} ≡ y$[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]?

where $p, q$ prime.

I can't see it from re-writing it as $y^{pq} = y + kpq$ for some integer $k$, as you cannot then divide by p or q.

Instead, re-writing as $y^{pq-1} ≡ 1$[mod $pq$] gives something like Fermat's Little Theorem. But does this not imply that $y^{pq-1} ≡ 1 [$mod $p$] OR $y^{pq-1} ≡ 1 [$mod $q$]? And then what about $-1$?

• Have you heard about the Chinese remainder theorem? – Arthur May 23 '14 at 11:11
• So it says that there exists a unique (mod $pq$) solution to the two congruences on the right? It feels like it goes in the opposite way to what is needed...? – timni May 23 '14 at 11:24
• CRT goes in the other direction. We don't need CRT for this. – user2357112 supports Monica May 23 '14 at 11:54

$$y^{pq} \equiv y \pmod{pq} \implies y^{pq}=y+kpq \implies y^{pq}=y+(kq)p \implies y^{pq} \equiv y \pmod p$$
Same logic goes for $q$. Incidentally, we don't need the assumptions that $p$ and $q$ are prime.
Hint: Since $x\equiv 0\mod pq\Rightarrow x\equiv 0\mod p$ and $x\equiv 0\mod q$ if $p,q$ are primes since say if $p|x$ and $q\not|x$ then $\displaystyle x=kpq\Rightarrow kp=\frac{x}{q}$ which is a contradiction.