0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Have you heard about the Chinese remainder theorem? $\endgroup$ – Arthur May 23 '14 at 11:11
  • $\begingroup$ 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...? $\endgroup$ – timni May 23 '14 at 11:24
  • 1
    $\begingroup$ CRT goes in the other direction. We don't need CRT for this. $\endgroup$ – user2357112 supports Monica May 23 '14 at 11:54
2
$\begingroup$

$$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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.