Exercise 2.5.5* (Find $a_1,a_2$ such that $a_1
ot \equiv a_2 \pmod m$, but $a_1^k \equiv a_2^k \pmod m$ for $k1$)

Question

Suppose that $m$ is a positive integer that is not square-free. Show that that there exist integers $a_1$ and $a_2$ such that $a_1
ot \equiv a_2 \pmod m$, but $a_1^k \equiv a_2^k \pmod m$ for all integers $k>1$.

Richard Ganaye · Accepted Answer

\begin{proof} Since $m$ is not square-free, there exists a prime $p$ such that $p^2 \mid m$, so we can write $m$ in the form
$$ m= p^a u,\qquad a\geq 2, \ p \wedge u = 1.$$

Take $a_1 = p$. Since $p^a \wedge u = 1$, the Chinese Remainder Theorem shows that there exists a unique $a_2 \in [\![0, m [\![$ such that
$$
\left\{
\begin{array}{ll}
a_2 \equiv p + p^{a-1} &\pmod{p^{a}},\
a_2 \equiv p &\pmod u.
\end{array}
ight.
$$
Suppose for contradiction that $a_2 \equiv a_1 \pmod {p^a}$, then $ 0 \equiv a_2 - a_1 = a_2 - p \equiv p^{a-1} \pmod {p^a}$, thus $p^a \mid p^{a-1}$, so $p \mid 1$: this is impossible. Therefore $a_2 
ot \equiv a_1 \pmod {p^a}.$ A fortiori, because $p^a \mid m$,
$$a_2 
ot \equiv a_1 \pmod {m}.$$

Now we prove that $a_1^k \equiv a_2^k \pmod m$ for all integers $k>1$.

Assume $k \geq 2$. Then, reducing modulo $p^a$, where $a\geq 2$
\begin{align*}
a_2^k &\equiv p^k(1 + p^{a-2})^k \
&\equiv p^k \left(1 + \binom{k}{1} p^{a-2} + \cdots + \binom{k}{i} p^{i(a-2)} + \cdots \binom{k}{k} p^{k(a-2)}ight)\
&\equiv p^k  + \sum_{i = 1}^k \binom{k}{i} p^{k +i(a-2)} \pmod {p^a}.
\end{align*}
Since $k \geq 2$ and $a \geq 2$, for all $i \geq 1$,
$$k+i(a-2) \geq k + a -2 \geq a.$$
Therefore 
$${a_2}^k \equiv p^k = {a_1}^k \pmod {p^a}.$$
Moreover, $a_2^k \equiv p^k = a_1^k \pmod u$. Since $p \wedge u = 1$,  $a_2^k \equiv p^k = a_1^k \pmod {p^a u}$, that is
$$a_2^k \equiv a_1^k \pmod m, \qquad 	ext{ if } k >1.$$

There exist integers $a_1$ and $a_2$ such that $a_1
ot \equiv a_2 \pmod m$, but for all integers $k>1$, $a_1^k \equiv a_2^k \pmod m$.

\end{proof}

For instance, if $m = 3^4\cdot 2 \cdot 5 = 810$, $a_1 = 3$ and $a_2$ is the solution between $0$ and $810$ of
$$
\left\{
\begin{array}{ll}
a_2 \equiv 3 + 3^3 = 30 &\pmod{81},\
a_2 \equiv 3 &\pmod {10},
\end{array}
ight.
$$
so $a_2 = 273$. Then
\begin{align*}
3 &
ot \equiv  273 \pmod {810},\
3^2 & \equiv 273^2  \equiv 9 \pmod{810},\
3^3 & \equiv 273^3  \equiv 27 \pmod{810},\
\ldots
\end{align*}

Exercise 2.5.5* (Find $a_1,a_2$ such that $a_1\not \equiv a_2 \pmod m$, but $a_1^k \equiv a_2^k \pmod m$ for $k>1$)

Answers

Comments

Exercise 2.5.5* (Find $a_1,a_2$ such that $a_1\not \equiv a_2 \pmod m$, but $a_1^k \equiv a_2^k \pmod m$ for $k>1$)

Answers

Comments

Add answer