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.
Fermat's Little Theorem --Fake Proof (talk contribs) 02:58, 2 April 2022 (UTC)
You can help Proof Wiki 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"