Number which is Square and Cube Modulo 7

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z$ be an integer.

Let $n$ be both a square and a cube at the same time.


Then either:

$n \equiv 0 \pmod 7$

or:

$n \equiv 1 \pmod 7$


Proof

Let $n = r^2 = s^3$ for some $r, s \in \Z$.

Then:

$n = \paren {m^2}^3 = \paren {m^3}^2 = m^6$

for some $m \in \Z$


There are $7$ cases to consider:

$(0): \quad m \equiv 0 \pmod 7$: we have $m = 7 k$
$(1): \quad m \equiv 1 \pmod 7$: we have $m = 7 k + 1$
$(2): \quad m \equiv 2 \pmod 7$: we have $m = 7 k + 2$
$(3): \quad m \equiv 3 \pmod 7$: we have $m = 7 k + 3$
$(4): \quad m \equiv 4 \pmod 7$: we have $m = 7 k + 4$
$(5): \quad m \equiv 5 \pmod 7$: we have $m = 7 k + 5$
$(6): \quad m \equiv 6 \pmod 7$: we have $m = 7 k + 6$


Using Congruence of Powers throughout, we make use of:

$x \equiv y \pmod 7 \implies x^j \equiv y^j \pmod 7$

for $j \in \Z_{>0}$.


First the easy cases:

\(\text {(0)}: \quad\) \(\displaystyle m\) \(\equiv\) \(\displaystyle 0 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle m^6\) \(\equiv\) \(\displaystyle 0 \pmod 7\)


\(\text {(1)}: \quad\) \(\displaystyle m\) \(\equiv\) \(\displaystyle 1 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle m^6\) \(\equiv\) \(\displaystyle 1 \pmod 7\)


It is sufficient to investigate the congruence modulo $7$ of the integers from $2$ to $6$.


Then we have:


\(\text {(2)}: \quad\) \(\displaystyle 2^3\) \(\equiv\) \(\displaystyle 8 \pmod 7\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 1 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 2^6\) \(\equiv\) \(\displaystyle 1 \pmod 7\)


\(\text {(3)}: \quad\) \(\displaystyle 3^2\) \(\equiv\) \(\displaystyle 9 \pmod 7\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 2 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3^6 = \paren {3^2}^3\) \(\equiv\) \(\displaystyle 1 \pmod 7\) from $(2)$


\(\text {(4)}: \quad\) \(\displaystyle 4^2\) \(\equiv\) \(\displaystyle 16 \pmod 7\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 2 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 4^6 = \paren {4^2}^3\) \(\equiv\) \(\displaystyle 1 \pmod 7\) from $(2)$


\(\text {(5)}: \quad\) \(\displaystyle 5^2\) \(\equiv\) \(\displaystyle 25 \pmod 7\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 4 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 5^6 = \paren {4^2}^3\) \(\equiv\) \(\displaystyle 2^3 = 8 \pmod 7\) from $(4)$
\(\displaystyle \) \(\equiv\) \(\displaystyle 1 \pmod 7\)


\(\text {(6)}: \quad\) \(\displaystyle 6^2\) \(\equiv\) \(\displaystyle 36 \pmod 7\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 1 \pmod 7\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 6^6 = \paren {6^2}^3\) \(\equiv\) \(\displaystyle 1 \pmod 7\)

Hence the result.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Number_which_is_Square_and_Cube_Modulo_7&oldid=412450"