Does the following hold for arbitrary positive integers $a$ and $n$: if $a^n-1$ is divisible by $n$ then so is $1+a+a^2+\cdots+a^{n-1}$? Let $a$ and $n$ be positive integers. Thanks to the equality
$$a^n-1=(a-1)(1+a+a^2+\cdots+a^{n-1}),$$
all divisors of $1+a+a^2+\cdots+a^{n-1}$ divide also $a^n-1$. The converse does not hold except for a very special case, but maybe always when the number $n$ happens to be a divisor of $a^n-1$ this particular divisor of it will divide also $1+a+a^2+\cdots+a^{n-1}$.
 A: Let $f(x)=x^n-1\in\Bbb Z_d[x]$, where $d\mid n$.
The claim $$d\mid a^n-1\Rightarrow d\mid a^{n-1}+\ldots+1$$ is the same as saying that $f(a)=0\Rightarrow (x-a)^2\mid f(x)$. This can be shown by the following derivative-multiplicity test:

Let $f(x)\in R[x]$ be a polynomial in any polynomial ring over any commutative ring $R$. Then if $f(a)=f'(a)=0$ we have $(x-a)^2\mid f(x)$.


Proof: Suppose that $f(a)=0$, then $f(x)=(x-a)g(x)$. Taking the formal derivative we get $$f'(x)=g(x)+(x-a)h(x)$$ If $f'(a)=0$, we get that $g(a)=0$, and so $(x-a)\mid g(x)$, in other words $$(x-a)^2\mid f(x)$$

The derivative is $f'(x)\equiv_d nx^{n-1}\equiv_d 0$, so trivially $f'(a)\equiv_d 0$. Therefore $$(x-a)\mid\frac{x^n-1}{x-1}=x^{n-1}+\ldots+x+1$$ and so $$a^{n-1}+\ldots+a+1\equiv_d 0$$ which holds for any $d\mid n$.
A: For any positive integer $n$, let  $S_n(x)=1+x+x^2+\cdots+x^{n-1}$. Let $A$ be the set of the positive integers $n$ such that $S_n(a)$ is a multiple of $n$ whenever $a$ is a positive integer and $a^n-1$ is a multiple of $n$. We will prove that all positive integers belong to $A$. This will be done by establishing that $A$ has the following properties:

*

*$1\in A$.


*Whenever $n\in A$ and $p$ is a prime number not dividing $n$, $p^kn\in A$ for all non-negative integers $k$.
Property 1 is obvious. To prove property 2, suppose $n\in A$ and $p$ is a prime number not dividing $n$. The statement that $p^0n\in A$ is trivial. Suppose now that $k$ is a non-negative integer such that $p^kn\in A$. We will show that $p^{k+1}n\in A$ too. Let $a$ be any positive integer such that $a^{p^{k+1}n}-1$ is a multiple of $p^{k+1}n$. We will show that $S_{p^{k+1}n}(a)$ is also a multiple of $p^{k+1}n$. Since $p^{k+1}n=pp^kn$, we see that $(a^p)^{p^kn}-1$ is a multiple of $p^{k+1}n$, hence $(a^p)^{p^kn}-1$ is a multiple of $p^kn$, and therefore so is $S_{p^kn}(a^p)$. We will next use the equalities
$$S_{p^{k+1}n}(a)=S_p(a)S_{p^kn}(a^p),$$
$$(a^p)^{p^kn}-1=(a^p-1)S_{p^kn}(a^p),$$
$$a^p-1=(a-1)S_p(a).$$
The needed conclusion can be derived from them in the following way. The validity of the conclusion is obvious from the first equality if $S_{p^kn}(a^p)$ is divisible by $p^{k+1}$. Suppose now that $S_{p^kn}(a^p)$ is not divisible by $p^{k+1}$. Then the second equality shows that $a^p-1$ is divisible by $p$, and this, together with the third one, implies the divisibility of $S_p(a)$ by $p$ because $p$ must divide $a-1$ or $S_p(a)$, but $S_p(a)\equiv 0\ (\textrm{mod }p)$ in the case when $p$ divides $a-1$ since
$$1\equiv a\equiv a^2\equiv\cdots\equiv a^{p-1}\ (\textrm{mod }p)$$
in that case. As $S_{p^kn}(a^p)$ is a multiple of $p^kn$, the first equality again yields the conclusion in question.
