Exercise 2.5.4* ($a^{k \overline{k}} \equiv a \pmod m$ for all integers $a$)

Question

Suppose that $m$ is square-free, and that $k$ and $\overline{k}$ are positive integers such that $k \overline{k} \equiv 1 \pmod{\phi(m)}$. Show that $a^{k \overline{k}} \equiv a \pmod m$ for all integers $a$.

Richard Ganaye · Accepted Answer

(I don't use the hint.)
\begin{proof} 
We know that $k \overline{k} \equiv 1 \pmod{\phi(m)}$, so there is some integer $\lambda$ such that
\begin{align}
k \overline{k} = 1 + \lambda \phi(m).
\end{align}

Since $m$ is square-free, the decomposition of $m$ in prime factors is
$$m = p_1p_2\cdots p_l,$$
where $p_1,p_2,\ldots,p_l$ are distinct primes. Then
\begin{align}
\phi(m) = (p_1-1)(p_2-1)\cdots (p_l - 1).
\end{align}

\begin{itemize}
\item Suppose first that $p_i 
mid a$. By Fermat's theorem, 
$$a^{p_i-1} \equiv 1 \pmod {p_i},\qquad i = 1,2,\ldots,l.$$
By (2), (or Problem 3), $\phi(p_i) = p_i - 1 \mid \phi(m)$, therefore
$$a^{\phi(m)} \equiv 1  \pmod {p_i},\qquad i = 1,2,\ldots,l.$$
This gives, using (1),
$$a^{k \overline{k}} = a^{1 + \lambda \phi(m)} \equiv a \pmod {p_i}.$$

\item If $p_i \mid m$, using $k \overline{k} 
e 0$, we obtain
$$a^{k \overline{k}} \equiv 0 \equiv a \pmod{p_i}.$$
\end{itemize}
In both cases, $a^{k\overline{k}} \equiv a \pmod {p_i}$, for all integers $a$, and for every index $i$.

Since $p_1,\ldots,p_l$ are distinct (thus relatively prime by pairs), $$a^{k\overline{k}} \equiv a \pmod{p_1p_2\cdots p_l},$$ that is
$$a^{k\overline{k}} \equiv a \pmod{m},$$
for all integers $a$.
\end{proof}

Exercise 2.5.4* ($a^{k \overline{k}} \equiv a \pmod m$ for all integers $a$)

Answers

Comments

Exercise 2.5.4* ($a^{k \overline{k}} \equiv a \pmod m$ for all integers $a$)

Answers

Comments

Add answer