Let $a$ and $n$ be two integers greater than $1$. Prove that if $n$ divides $(a-1)^k$ for some integer $k\geq 2$, then $n$ also divides $a^{n-1}+a^{n-2}+\cdots+a+1$.
Problem
Source: Romania TST 5 2009, Problem
Tags: modular arithmetic, number theory proposed, number theory
04.05.2012 20:49
Remark that we need $\frac{a^n - 1}{a-1} \equiv 0 \pmod{n}$. Then remark that $v_p(a-1) \cdot k \ge m$. If $p$ is an odd prime we have $v_p(a^n - 1) = v_p(a-1) + m$ by LTE. But then $v_p \left ( \frac{a^n - 1}{a-1} \right ) = m$ so $p^m$ divides it. Hence we have shown all odd primes work out in the divisibility. Now suppose $2|n$, so that $a$ is odd. But by LTE $v_2(a^n - 1) = v_2(a-1) + v_2(a+1) + v_2(n) - 1$ so $v_2 \left ( \frac{a^n - 1}{a-1} \right ) = v_2(a+1) + v_2(n) - 1 \ge v_2(n)$, so enough factors of $2$ divide it. Hence the result follows.
01.01.2022 03:19
Let $p$ be a prime divisor of $n.$ It suffices to prove that $$\nu_{p}(n)\le\nu_{p}(a^{n-1}+a^{n-2}+\dots+a+1)=\nu_{p}\left(\frac{a^n-1}{a-1}\right),$$which is true by Theorem 6.22 of Number Theory: Concepts and Problems since $p\mid a-1.$ $\square$
20.07.2022 19:08
Isn't this problem just blind LTE? Let a prime $p \mid n$. Then $p$ divides $a-1$, so $$\nu_p\left(\frac{a^n-1}{a-1}\right) = \nu_p(a^n - 1) - \nu_p(a-1) = \nu_p(n)$$by LTE, as required.