Showing there isn't such an integer $a \not\equiv 1$ that $a^7 \equiv 1 \pmod{21}$

Question

Establish whether there exists an integer $a \in \mathbb{Z}, a \not\equiv 1$ such that $a^7 \equiv 1 \pmod{21}$

The first thing I tried was trying to compute the result of $a^7$ for some small $a$'s. This is what I found:

By breaking up $a^7$ into $a^2\cdot a^2 \cdot a^2 \cdot a$, I made it easier to find that: $$2^7 = 128 \equiv 2 \pmod{21}\\ 3^7 = 3^23^23^23 \equiv 81^23\equiv3 \pmod{21}\\ 4^7 \equiv \cdots\equiv 4 \pmod{21}\\\vdots\\ 7^7\equiv \cdots \equiv 7 \pmod{21}$$ I only did the computations until $7$ because I could clearly see a pattern. It appears as if: $$\forall a \in \mathbb{N}, a^7\equiv a \pmod{21} \tag{conjecture}$$

I think that, if I find a way to prove my conjecture, I'd be done with the problem. I tried to prove it by induction to no avail, so maybe that's not the right path. I thought that by factorizing $a^7-a$ and trying to find a relationship between $(a-1)^7$ and $a^7$ I could have had some luck, but it didn't happen.

Any inputs?

Answer 1

The conjecture is true because $a^7\equiv a\bmod21$ is equivalent to $a^7\equiv a\bmod7$ and $a^7\equiv a\bmod3$ by the Chinese remainder theorem, and both the latter statements are true for all $a$ by Fermat's little theorem.

Answer 2

Well, you could just test them all. For any integer $a$ there must be an $i = 0, 1,2,....,20$ so that $a\equiv i\pmod{21}$ and $a^7\equiv i^7\pmod {21}$ and none of $0^7,2^7,....., 20^7$ are congruent to $1\pmod{21}$ and only $1^7\equiv 1 \pmod {21}$..

That's not satisfying as it's unlikely anyone want to take the effort or that anyone will be sasfied by such a brute force answer. (but it's always a last ditch option.)

....

Alternatively $a^7\equiv 1 \pmod {21}$ is only possible if $\gcd(a,21)= 1$. [Because $\gcd(a,21)|a^7$ so if $\gcd(a,21)\ne 1$ then $\gcd(a,21)\not \mid a^7-1$.]

And by Euler's Theorem $\phi(21) = \phi(3)\phi(7)=2*6=12$ and so $a^{12}\equiv 1\pmod {21}$. So if $a^7\equiv 1$ then $(a^7)^2\equiv a^{14}\equiv a^{12}a^2\equiv 1*a^2\equiv a^2 \equiv 1$ and then $(a^2)^4\equiv a^8\equiv a*a^7\equiv a*1\equiv a \equiv 1 \pmod{21}$.

A little bit more structure would be to set up an equation to find a $k$ so that $k\equiv 1 \pmod 7$ and $k \equiv 0\pmod {12}$ or an $m$ so that $m\equiv 0\pmod 7$ and $m\equiv 1\pmod {12}$ then $a^k\equiv a^1\equiv a^0\pmod{21}$.

For instance $k = 36$ or $m = 49$. Then $a^{36}\equiv (a^7)^5*a\equiv a\pmod {21}$ but $a^{36}\equiv (a^{12})^3 \equiv 1\pmod {21}$ so $a\equiv 1 \pmod{21}$. Or $a^{49}\equiv (a^7)^7\equiv 1 \pmod {21}$ but $a^{49}\equiv (a^{12})^4*a \equiv a\pmod{21}$.

....

Alterantively Fermat's Little Theorem and the Chinese Remainder Theorem lets us consider smaller numbers:

$a^7\equiv 1 \pmod {21}$ means that

$a^7 \equiv 1 \pmod 3$ and that $a^7\equiv 1 \pmod 7$.

And thus $a \not \equiv 0 \pmod 3$ and $a\not \equiv 0\pmod 7$. SO by FLT:

$a^2\equiv 1\pmod 3$ and $a^7=a^6*a\equiv a\pmod 3$ so $a \equiv 1 \pmod 3$.

And $a^6\equiv 1 \pmod 7$ and $a^7\equiv a^6*a\equiv a \pmod 7$ so $a\equiv 1 \pmod 7$.

By CRT there is only one solution $\pmod {21}$ where $a\equiv 1\pmod 7$ and $a \equiv 1\pmod 3$ and that is $a\equiv 1\pmod {21}$ is clearly one solution, and as it is the only solution we can conclude.

The onlly integers where $a^7\equiv 1\pmod {21}$ are where $a \equiv 1 \pmod {21}$.