(i) Find all integers $n \geqslant 1$ such that $n$ divides $2^{n}-1$.

(ii) Find all odd integers $n \geqslant 1$ such that $n$ divides $3^{n}+1$.

## - Solution -
(i) Let $n>1$ such that $n$ divides $2^{n}-1$. It is clear that $n$ is odd. Let $p$ be the smallest prime factor of $n$, which is therefore odd. Then $2^{n} \equiv 1 \bmod p$. Let $\omega$ be the order of 2 modulo $p$. Then $\omega$ divides $n$. On the other hand, by Fermat's Little Theorem, $2^{p-1} \equiv 1 \bmod p$. Thus $\omega$ divides $p-1$. Given the condition on $p$, we necessarily have $\omega=1$. Then $2 \equiv 1 \bmod p$, which is absurd. Therefore, we must have $n=1$.

(ii) Let $n>1$ such that $n$ divides $3^{n}+1$. Let $p$ be the smallest prime factor of $n$, which is therefore odd, and thus $p>3$. Then $3^{2 n} \equiv 1 \bmod p$. Let $\omega$ be the order of 3 modulo $p$. Then $\omega$ divides $2 n$. On the other hand, by Fermat's Little Theorem, $3^{p-1} \equiv 1 \bmod p$. Thus $\omega$ divides $p-1$. We deduce that $\omega$ divides $\operatorname{gcd}(2 n, p-1)$. Given the condition on $p$, we necessarily have $\omega=1$ or 2. In the first case, $3 \equiv 1 \bmod p$ and thus $p=2$, which is excluded. In the second case, $3^{2} \equiv 1 \bmod p$ and thus $p$ divides 8, which is also excluded. We conclude that $n=1$.

## 3 Intermediate: Algebra

We refer to the polynomial course available on the Animath website for details and complements (see the links at the top of page 14).

## 1 First TD on Polynomials

## - Statements -