What is the size of the set $\{ 0^{42}\pmod{101}, 1^{42}\pmod{101}, 2^{42} \pmod{101},...,100^{42}\pmod{101}\}$

Question

What is the size of the set $\{ 0^{42}\pmod{101}, 1^{42}\pmod{101}, 2^{42} \pmod{101},...,100^{42}\pmod{101}\}$? How would you even start the problem? By the way, I got this problem from my number theory workbook in the chapter "primitive roots". I already have a guess that it's $51$ since the first and last one will always be the same as $a^{42}$ is equal to $(101-a)42$. However, how can you prove all the others are distinct from each other?

Answer 1

Use the fact that $101$ is prime, so for every $x \in \{1,...,100\}$ there exists $x^{-1} \in \{1,...,100\}$ such that $xx^{-1} \equiv 1 \pmod{101}$.

Therefore, if for any two elements $a,b \in \{1,...,100\}$ we have $a^{42} \equiv b^{42} \pmod{101}$, this implies that $(ab^{-1})^{42} \equiv 1 \pmod{101}$. Conversely, note that if $l \in \{1,...,100\}$ satisfies $l^{42} \equiv 1 \mod 101$ then for any $a \in \{1,...,101\}$ we will have $a^{42} \equiv (al)^{42} \equiv (al^2)^{42} \ldots \pmod{101}$.

That means that identifying elements like $l$ are the way to proceed.

---

But for which $l$ is it true that $l^{42} \equiv 1 \pmod{101}$? Note that $l^{100} \equiv 1 \pmod{101}$ from the usual Fermat theorem. Using Bezout lemma and the fact that $\gcd(42,100) = 2$ we get that $l^2 \equiv 1 \pmod{101}$.

Therefore, $l = \pm 1 = 1 \pmod{101}$ or $100 \pmod{101}$.

Now, note that to every $a \in \{1,...,100\}$ associates the element $al = 101-a$ such that $a^{42} \equiv (al)^{42} \pmod{101}$. Conversely, if two elements have this relation then one must be $101$ minus the other.

This leads to $50$ different elements in the set. Adding in $0$ from $0^{42}$ gives the result $51$.