Given is an positive integer $a>2$ a) Prove that there exists positive integer $n$ different from $1$, which is not a prime, such that $a^n=1(mod n)$ b) Prove that if $p$ is the smallest positive integer, different from $1$, such that $a^p=1(mod p)$, then $p$ is a prime. c) There does not exist positive integer $n$, different from $1$, such that $2^n=1(mod n)$
Problem
Source: Romania NMO 2021 grade 12
Tags: number theory
Filipjack
25.04.2021 10:47
$a)$ Let $p$ be a prime such that $p \mid a-1.$ One may easily prove using LTE or Binomial Theorem that $a^{p^2} \equiv 1 \pmod {p^2}.$ $b)$ Assume $p$ is not a prime and let $q$ be its smallest prime divisor. From $a^p \equiv 1 \pmod p $ it follows that $\gcd(a,q)=1$ and $a^p \equiv 1 \pmod q.$ We also know, by Fermat, that $a^{q-1} \equiv 1 \pmod q$. So $a^{\gcd(p,q-1)} \equiv 1 \pmod q.$ But $\gcd(p,q-1)=1$ (assuming the contrary we would get that $p$ has a prime divisor smaller than $q$, which is a contradiction), so $a \equiv 1 \pmod q$. Therefore $a^q \equiv 1 \pmod q,$ which contradicts the minimality of $p,$ so $p$ must be a prime.
Note: the arguments used to prove $b)$ works for $a=2$ too.
) this number must be a prime so, by Fermat, $2^p \equiv 2 \pmod p.$ Thus $1 \equiv 2 \pmod p,$ which is impossible. Therefore there does not exist such an $n.$