Let $n \geq 2$ be natural number. Prove, that $(1^{n-1}+2^{n-1}+....+(n-1)^{n-1})+1$ divided by $n$ iff for any prime divisor $p$ of $n$ $p| \frac{n}{p}-1 $ and $(p-1)| \frac{n}{p}-1$.
Problem
Source:
Tags: number theory proposed, number theory
08.09.2010 10:56
Ovchinnikov Denis wrote: Let $n \geq 2$ be natural number. Prove, that $(1^{n-1}+2^{n-1}+....+(n-1)^{n-1})+1$ divided by $n$ iff for any prime divisor $p$ of $n$ $p| \frac{n}{p}-1 $ and $(p-1)| \frac{n}{p}-1$. I think here is notation problem.What do you mean by $p|\frac n p-1$ Will it be $p|(\frac n p)-1$(Legendre Symbol)?
08.09.2010 11:20
mathmdmb wrote: Ovchinnikov Denis wrote: Let $n \geq 2$ be natural number. Prove, that $(1^{n-1}+2^{n-1}+....+(n-1)^{n-1})+1$ divided by $n$ iff for any prime divisor $p$ of $n$ $p| \frac{n}{p}-1 $ and $(p-1)| \frac{n}{p}-1$. I think here is notation problem.What do you mean by $p|\frac n p-1$ Will it be $p|(\frac n p)-1$(Legendre Symbol)? $p$ is divisor of $n$ so $ (\frac{n}{p})=0$ if it is Legendre symbol. So in problem it is fractional $\frac{n}{p}$
08.09.2010 14:15
I've seen this problem in a book, but it has written Iran 2005
08.09.2010 14:35
amparvardi wrote: I've seen this problem in a book, but it has written Iran 2005 I see at two different set's and it both it is SRMC May be it was one problem??
08.09.2010 20:18
amparvardi wrote: I've seen this problem in a book, but it has written Iran 2005 Hello Amir, i too saw a similar problem but that stated $n|1^n+2^n+...+(n-1)^n-1$
14.01.2018 00:20
This is a very nice problem, which is sitting, without any solution. Here is one: ``If'' part: Let us begin by the if part. Suppose, $p\mid \frac{n}{p}-1$; and, $p-1 \mid \frac{n}{p}-1$. Notice that, $\bullet$ $n$ is square-free; since, had, $p^2 \mid n$ been true; we would have, for, $n=p^2 \cdot k$, $$ p \mid \frac{n}{p}-1 \implies p\mid p\cdot k -1, $$a contradiction. $\bullet$Also, $p-1\mid n-1$; since, $$ p-1 \mid \frac{n-p}{p}\implies p-1\mid n-p \implies p-1 \mid n-1; $$where, the first divisibility holds, since, $(p,p-1)=1$. $\bullet$ Finally, $p \mid \frac{n}{p}-1 \implies \frac{n}{p}-1 = kp\implies n=kp^2 + p$. Now, suppose, $p$ is a prime divisor of $n$. It boils down to proving that, $$ p \mid \sum_{i=1}^{n-1}i^{n-1} + 1. $$Using Fermat's theorem, we have, $i^{n-1}\equiv 1 \pmod{p}$, if, $i\not\equiv 0\pmod{p}$; and, $i^{n-1}\equiv 0\pmod{p}$, if, $p\mid i$. Hence, the sum, can be written as, $$ \sum_{i=1}^{n-1}i^{n-1} + 1 \equiv -1 \cdot \frac{n}{p}+1=-kp-1+1\equiv 0\pmod{p}, $$thus, we are done. Only if part: Now, suppose, the given divisibility holds. Take a prime $p$, such that, $p\mid n$; and, note that, using, $a^p\equiv a\pmod{p}$; we have, $$ i^{n-1}\equiv i^{p\frac{n}{p}-1}\equiv (i^p)^{\frac{n}{p}}\cdot i^{-1}\equiv i^{\frac{n}{p}-1}. $$Also, note that, this is still valid, even though, $p\mid i$ ($n/p>1$, so, $-1$ is not an issue). Hence, we have, $$ p\mid 1^{\frac{n}{p}-1}+2^{\frac{n}{p}-1}+\cdots+(n-1)^{\frac{n}{p}-1}+1. $$Let, $\frac{n}{p}-1 = (p-1)q+r$; where, $0\leq r\leq p-2$. We want to show that, $r=0$. For the sake of contradiction, suppose, $r\neq 0$; thus, $r\in\{1,2,\dots,p-2\}$. Lemma: For any prime $p$; and, $k\in\{1,2,\dots,p-2\}$, we have, $$ 1^k + 2^k +\cdots + (p-1)^k \equiv 0 \pmod{p}. $$Proof: We omit the proof, but, it simply relies on the observation that, the primitive root, $g$, generates, $\mathbb{Z}_p$; or more compactly, $$ \left\{g^i:i=1,2,\dots,p-1\right\} = \{1,2,\dots,p-1\} \pmod{p}. $$Using the lemma, we have, \begin{align*} 1^{\frac{n}{p}-1}+2^{\frac{n}{p}-1}+\cdots+(n-1)^{\frac{n}{p}-1}+1 &\equiv 1^r + 2^r +\cdots + (n-1)^r +1 \pmod{p}\\ &\equiv \underbrace{1^r + 2^r +\cdots + (p-1)^r}_{\equiv 0 \pmod{p}} + \cdots + (n-1)^r + 1 \pmod{p}\\ &\equiv 1 \pmod{p}, \end{align*}thus, a contradiction, where, the equivalence in modulo $p$, underbraced above, follows from the lemma. Now, finally, using the fact that, $p-1\mid n-1$; we have, $$ 1^{n-1}+2^{n-1}+\cdots+(n-1)^{n-1}+1 \equiv -1\cdot \frac{n}{p}+1; $$hence, we must have, $$ p\mid \frac{n}{p}-1, $$as desired.
14.01.2018 00:23
Nice!!!!