Find the set $S$ of primes such that $p \in S$ if and only if there exists an integer $x$ such that $x^{2010} + x^{2009} + \cdots + 1 \equiv p^{2010} \pmod{p^{2011}}$. Brian Hamrick.
Problem
Source: ELMO Shortlist 2010, N5
Tags: modular arithmetic, number theory proposed, number theory
05.07.2012 09:29
I will prove that $S=\{p|p=2011k+1 for some integer k\}$. First we note that $2011$ is a prime number. 1. When $p|x-1$, the LTE implies $ord_p LHS=ord_p 2011$, contradiction. (To those who don't know LTE, see here. http://www.artofproblemsolving.com/Forum/viewtopic.php?f=721&t=401494) 2. Otherwise. $p|x^{2010}+x^{2009}+\cdots+1|x^{2011}-1$. Take the primitive root $a$ in $mod\ p$, and let $x=a^d$ where $p-1$ doesn't divide $d$. Then $p-1|2011d$ implies $2011|p-1$. Thus $S\subset\{p|p=2011k+1 for some integer k\}$. For those satisfies the condition, we can choose $x_1$ not congruent to $1$ mod $p$ such that $p|x^2011-1$. We wanna find $x$ such that $x\equiv x_1$ and $x^{2011}\equiv (x_1-1)p^{2010}\ \ \(mod\ p^{2011})$. To prove this, I will show a lemma: (Lemma) Let $a,b,x,d,k$ be an integer, and $p$ be a prime where $a-b,x,k$ is not divisible by $p$. Then $(x+ap^d)^k$ and $(x+bp^d)^k$ is not congruent with $mod\ p^{d+1}$. (proof) \[(x+ap^d)^k-(x+bp^d)^k\equiv(x^k+kap^d)-(x^k+kbp^d)\equiv k(a-b)p^d\ (mod\ p^{d+1})\] Then, we can use this lemma inductively, and get the desired $x$. Done. Remark We can show that $S$ is an infinite set without Dirichlet. (Proof) Suppose $S$ is finite for the sake of contradiction. Let all the elements of $S$ be $p_1,p_2,\cdots,p_m$. Take the prime factor $q$ of \[(2p_1p_2\cdots p_m)^{2011}-1(\equiv 1\ (mod2011))\]. If it is not a factor of $(2p_1p_2\cdots p_m)-1$, then $2011|q-1$. Also when all the factor is the factor of $(2p_1p_2\cdots p_m)-1$, Take $X=\frac{(2p_1p_2\cdots p_m)^{2011}-1}{(2p_1p_2\cdots p_m)-1}\equiv 2011(mod\ (2p_1p_2\cdots p_m)-1)$ which is impossible.
12.03.2016 18:51
The answer is all $p \equiv 1 \pmod{2011}$. First, note that if $x$ satisfies the problem condition, then we in particular have $\Phi_{2011}(x) \equiv 0 \pmod p$ which implies $p \equiv 1 \pmod{2011}$. Conversely, suppose $p \equiv 1 \pmod{2011}$ and fix an $a \pmod p$ with order $2011$ (hence $a \not\equiv 1 \pmod p$). Let $A = \left\{ x \pmod{p^{2011}} \mid x \equiv a \pmod{p} \right\}$ and $B = \left\{ x \pmod{p^{2011}} \mid x \equiv 0 \pmod{p} \right\}$. We claim $\Phi_{2011} : A \to B$ is injective: indeed if $\Phi_{2011}(x) \equiv \Phi_{2011}(y) \pmod{p^{2011}}$ then \[ (x^{2011}-1)(y-1) \equiv (y^{2011}-1)(x-1) \pmod{p^{2011}} \]hence \[ (x-y)\left( xy\sum_k x^{2010-k}y^k - \sum_k x^{2011-k}y^k + 1 \right) \equiv 0 \pmod{p^{2011}}. \]The sum in parentheses is nonzero modulo $p$ because it equals \begin{align*} a^2 \cdot 2011a^{2010} - 2012a^{2011} + 1 &= 2011a^{2012} - 2012a^{2011} + 1 \\ &\equiv 2011a - 2012 + 1 \pmod p\\ &= 2011(a-1) \\ &\not\equiv 0 \pmod p. \end{align*}This proves $\Phi_{2011} : A \to B$ is injective; but now $|A| = |B|$ implies surjectivity too. Since $p^{2010} \in B$, this completes the proof.
13.04.2017 22:48
Does this work? Quote: $2011$ is prime. Easily by CycPoly properties we see that $p=2011$ or $2011\mid p-1$. By LTE $p=2011$ is a bust. Now the construction. Because $x^{p}-x$ splits and is squarefree in $\mathbb F_p$, and $p\equiv 1\pmod{2011}\implies \Phi_{2011}(x)\mid x^p-x$, we see that not only does $\Phi_{2011}(x)$ have roots in $\mathbb F_p$, but it splits completely and squarefreely in said field. Now let $Q(x)\equiv \Phi_{2011}(x)-p^{2010}$. Because we have $\Phi_{2011}(x)\equiv Q(x)\pmod{p^k}$ when $1\leq k<2011$, and because of the considerations above, we can stick $Q(x)$ into good ol' Hensel's Lemma to get our $x\pmod{p^{2011}}$
03.06.2017 22:41
05.07.2020 14:58
We claim that $p \in S \iff p \equiv 1 \pmod{2011}$ Proof of Necessity Denote by $\Phi_{2011} (X)$ , the $q$-th cyclotomic polynomial . We have $$ \exists X \text { such that } \Phi_{2011} (X) \equiv p^{2010} \pmod {p^{2011}} \implies p \mid \Phi_{2011} (X) \implies p \equiv 1 \pmod {2011} $$ Proof of Sufficiency We start off with a crucial claim . Claim: The number of distinct residues $X$ modulo $p$ satisfying $\Phi_{2011} (X) \equiv 0 \pmod{2011}$ are exactly $2010$ Proof : Consider a primitive root $g$ modulo $p$ and a $X$ such that $\Phi_{2011} (X) \equiv \pmod {p} $ . Let $X= g^ {\alpha}$ with $\alpha \in \{0,1,2, \dots p-1\}$ Note that $\alpha \neq 0$ for obvious reasons . We need $$ \Phi_q (g^ {\alpha}) \equiv 0\pmod {p} \implies g^ {2011 \cdot \alpha} \equiv 1 \pmod p \implies \alpha \equiv 0 \pmod { \frac {p}{2011}}$$ Since , $\alpha \in \{0,1,2, \dots p-1\} \implies$ there are exactly $2010$ solutions for $\alpha$ . Next we consider the equation $\Phi_{2011} (X)-p^{2010}$$\pmod {p^r}$ for $r \geq 1$ . We claim that atleast one of the $2011$ solutions is not a zero of $\Phi'_{2011} (X)$ modulo $p$. Then we would be obviously done by Hensel's Lemma . FTSOC assume not . Note that $\Phi'_{2011} (X)$ is a $2009$ degree polynomial . By Lagrange's theorem, it can have atmost 2009 zeroes modulo $p$ . We're done !
01.08.2021 23:14
Let $F(x)=\sum_{k=0}^{2010}x^i=\varPhi_{2011}(x)$ be the $2011$-th cyclotomic polynomial. We make use of the following fact from cyclotomic polynomials: If $\varPhi_n(x)$ has zero modulo prime $p$ then either $p|n$ or $p\equiv 1(\text{mod}\ n)$. In our case $n=2011$, so that either $p=2011$ or $p\equiv 1(\text{mod}\ 2011)$. In the first case it is easy to show that $p^2\nmid F(x)$, so that we can not have $F(x)\equiv p^{2010}(\text{mod}\ p^{2011})$. In the second case it can be inductively shown that $p^{k+1}|F(x^{p^{k}})$ for each integer $k\geq 0$. Moreover, if $F(y)\equiv 0(\text{mod}\ p^{k})$ for some positive integer $k$, then $F'(y)\not\equiv 0(\text{mod}\ p)$ (this is because the polynomial $x^{2011}-1$ does not have multiple roots modulo $p$). This allows us to write $F(y+p^kz)=F(y)+p^kzF'(y)(\text{mod}\ p^{k+1})$ for each integer $z$. Since $p\nmid F'(y)$, there exist some integer $z_0$ such that $z_0F'(y)\equiv 1(\text{mod}\ p)$ and therefore $F(y+p^kz_0)\equiv p^k(\text{mod}\ p^{k+1})$. So the answer to the problem is all the primes congruent to 1 modulo $2011$.
01.08.2021 23:55
Redacted
17.09.2021 17:55
Zhero wrote: Find the set $S$ of primes such that $p \in S$ if and only if there exists an integer $x$ such that $x^{2010} + x^{2009} + \cdots + 1 \equiv p^{2010} \pmod{p^{2011}}$. Brian Hamrick. The answer is all primes $p$ which are of the form $2011k+1$ Lemma:When $\gcd(a,b)=1$,any prime factor $q$ of $\frac{a^p-b^p}{a-b}$ is of the form $1+kp$ or equal to $p$ By the Lemma,$p$ must be of the form $2011k+1$(since $p=2011$ doesn't work) Now to show that $p=2011k+1$ works we will use Hensel's Lemma. Define $\mathbf{F}(x):=x^{2010} + x^{2009} + \cdots + 1$ and clearly $\mathbf{F}'(X) \not \equiv 0 \pmod p$ since $\deg(\mathbf{F}'(X))=2009>p=2011k+1$ Suppose that there exists an integer $X$ such that $ \mathbf{F}(X) \equiv 0 \pmod {p^k}$ then $\mathbf{F}(X+p^k \mathbf{F}'(X)^{-1}) \equiv \mathbf{F}'(X)+p^k \mathbf{F}'(X)^{-1} \mathbf{F}'(X) \equiv p^k \pmod {p^{k+1}} $,hence we are done.$\blacksquare$