1
$\begingroup$

Let $p$ and $q$ be two different prime numbers, and $n = p \cdot q$. Let $a$ be a number relative prime to $n$. Use Fermat's little theorem and the Chinese remainder theorem to show that \begin{equation} a^{(p-1)(q-1)} \equiv 1 \pmod{n} \end{equation} By the Chinese remainder theorem I can write this as the system of linear congruences \begin{align*} \begin{cases} a^{(p-1)(q-1)} \equiv 1 \pmod{p} \\ a^{(p-1)(q-1)} \equiv 1 \pmod{q} \end{cases} \end{align*} Assuming that the inverse is simply 1 in both cases, that yields the solution \begin{align*} x \equiv a^{(p-1)(q-1)}(q+p) \pmod n \end{align*} Fermat's little theorem gives that \begin{align*} a^{p-1} \equiv 1 \pmod p \\ a^{q-1} \equiv 1 \pmod q \\ \end{align*} I don't really understand how to combine these to get the desired result.

$\endgroup$
  • $\begingroup$ In my course we called it the Little Fermat improved theorem ! There is a hidden Gauss lemma in other proofs ;) $\endgroup$ – Maman Oct 6 '16 at 17:46
3
$\begingroup$

So close! Just raise the first equation to the power of $q-1$ and raise the second equation to the power of $p-1$. Now, you can apply the Chinese Remainder Theorem.

$\endgroup$
  • 1
    $\begingroup$ Thanks! I felt like I was very close, but I just couldn't see the it. $\endgroup$ – SBS Oct 6 '16 at 17:37
1
$\begingroup$

Note that $\phi(n) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$, where $\phi$ is the Euler Totient Function. Also we know that whenever $(a,n) = 1$

$$a^{\phi(n)} \equiv 1 \pmod n$$

$\endgroup$
  • 1
    $\begingroup$ I know, but I don't think I was supposed to use the Euler Theorem since we haven't learned about that yet. $\endgroup$ – SBS Oct 6 '16 at 17:36
1
$\begingroup$

Given, $p$, $q$ are prime, $\phi(pq)=(p-1)(q-1)$ because every integer less or equal to a prime is relatively prime with that integer. Therefore, $\phi(p)=(p-1)$ and since it is $\phi$ is multiplicative, $\phi(pq)=(p-1)(q-1)$. Euler's theorem states that $a^{ϕ(n)}≡1 (mod n)$, when $(a,n)=1$. Therefore, $a^{(p-1)(q-1)}≡1 (mod n)$.

$\endgroup$
  • $\begingroup$ This is a very funny site, it supports latex formulas! Look, how well your answer looks now. I edited it! $\endgroup$ – peterh Mar 17 '18 at 19:07

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.