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\) \(\ds m\) \(\equiv\) \(\ds 0 \pmod 7\)
\(\ds \leadsto \ \ \) \(\ds m^6\) \(\equiv\) \(\ds 0 \pmod 7\)


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


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


Although this article appears correct, it's inelegant. There has to be a better way of doing it.
In particular: Fermat's Little Theorem --Fake Proof (talk contribs) 02:58, 2 April 2022 (UTC)
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Then we have:


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


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


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


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


\(\text {(6)}: \quad\) \(\ds 6^2\) \(\equiv\) \(\ds 36 \pmod 7\)
\(\ds \) \(\equiv\) \(\ds 1 \pmod 7\)
\(\ds \leadsto \ \ \) \(\ds 6^6 = \paren {6^2}^3\) \(\equiv\) \(\ds 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=566133"