Number which is Square and Cube Modulo 7
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:
\((0):\quad\) | \(\displaystyle m\) | \(\equiv\) | \(\displaystyle 0 \pmod 7\) | ||||||||||
\(\displaystyle \leadsto \ \ \) | \(\displaystyle m^6\) | \(\equiv\) | \(\displaystyle 0 \pmod 7\) |
\((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:
\((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\) |
\((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)$ |
\((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)$ |
\((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\) |
\((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
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Problems $2.1$: $5$