About Euler’s Algorithm
Say a moduler $p$, we can form a gourp $G$ by gathering around all the integers samller than $p$ that are prime to $p$. It should be a group.
Then we focus on any cosubgroup $H$, such that we can form a cyclic group $H$. The point is, any subgroup should divide the whole group by Lagrange’s theorem.
$$ siz(H) |siz(G) $$The interesting point is, if we let $H$ to be the cyclic group of an element, say $a$.
$$ order(a)=siz(H)|siz(G) $$We konw that $siz(G)=\phi(p)$, and also,
$$ a^{order(a)}\equiv 1 \pmod p $$So, apparently,
$$ a^{siz(G)} \equiv 1 \pmod p \\ a^{\phi(p)} \equiv 1 \pmod p $$There also a question asking what is the last digit of $7^{7^{7^7}}$
$$ 7^{7^{7^7}}\equiv ?\pmod {10} $$So we know $\phi(10)=4$, the problem becomes to know
$$ 7^{7^7} \equiv ? \pmod 4 $$So we know $\phi(4)=2$, the problem becomes to know,
$$ 7^7 \equiv ? \pmod 2 $$It is 1.
$$ 7^1 \equiv 3 \pmod 4 $$$$ 7^3 \equiv 3 \pmod {10} $$Proof of infinite prime with last digit of 1
So prove
$$ p \equiv 1 \pmod 5 $$Let
$$ p | \frac{x^5-1}{x-1} = 1+x+x^2+x^3+x^4 $$By the way this poly is called cyclotomic poly, 分圆多项式, which has a primitive 5’th roots of 1.
So $p|x^5-1$,
$$ x^5 \equiv 1 \pmod p $$The point is, the order of $x$,
$$ order(x) | 5 $$If $order(x)=1$
$$ x \equiv 1\pmod p $$Also,
$$ 1+1+1+1+1\equiv 0 \pmod p $$So,
$$ p=5 $$If $order(x)=5$
$$ 5 | (p-1) $$Say,
$$ p \equiv 1 \pmod 5 $$
Then we can apply Euler’s algorithm,
Let,
$$ p_1,p_2,...,p_k $$be primes that $p_i\equiv 1 \pmod 5$
Let,
$$ x=5p_1p_2...p_k $$Then any $p|(1+x+x^2+x^3+x^4)$, is nor 5 or any of $p_i$, but with the property that $p\equiv 1 \pmod 5$
Exercise
$\infty$ primes that $p \equiv 1\pmod 8$
Richard also gives a hint that using $x^4+1$
Also applying the same strategy, we get, $p=2$ or $order(x)=8$.
Then the same,
$$ x=2p_1p_2...p_k $$