# $p$-adic valuation of $x^n+1$[or how many times does a prime number divides $x^n+1$]

Let $p$ be a prime, and let $t \in \mathbb{Q}$ be an arbitrary rational number. By the term $p$-adic valuation of $t$; denoted by $v_p(t)$, we mean how many times the prime number $p$ divides $t$.

For example:

$v_5(250 )= 3 \ , \ \$ $v_7( 42 )= 1 \ \ \ \ \ , \ \ \$ $v_3( 81 )= 4 \ \ \ \ \ , \ \$ $v_2(100^3)= 6 \ , \ \$ $v_3(108 )= 3 \ , \ \$

$v_5(\dfrac{75}{91})= 2 \ , \ \$ $v_7(\dfrac{11}{98})=-2 \ , \ \$ $v_3(\dfrac{11}{15})=-1 \ , \ \$ $v_2(\dfrac{17}{24})=-3 \ , \ \$ $v_3(\dfrac{18}{41})= 2 \ . \ \$

Let $p$ be a prime, $x$, $y$ are integers. If $v_p(x^n+1)=v_p(y^n+1)$ for every positive integer $n$ and $v_p(x^n+1)$ is not constant for large $n$, can we conclude $x=y$?

• When you say $\Bbb Z_p$, do you mean the $p$-adic integers, or the integers modulo $p$? (Side note: does it matter?) – Arthur Aug 1 '17 at 7:31
• p-adic integer, I want to avoid the trivial cases e.g $x=p, y=p^2$ – zzy Aug 1 '17 at 7:33
• I assume you want to avoid $x = p+1, y = 2p+1$ as well (which works as long as $p$ is odd)? – Arthur Aug 1 '17 at 7:35
• You want $x$ a quadratic non-residue modulo $p$ so that $x^n \equiv - 1 \bmod p$ for some $n$. Otherwise $v_p(x^n+1) = 0$ for every $n$. – reuns Aug 1 '17 at 7:35
• The question reduces to find $y$ with $v_p(y^{b}+1) = v_p(x^b+1)$ where $2b$ is the order of $x \bmod p$ – reuns Aug 1 '17 at 7:51

Lemma(1):

• Part(a) Let $p$ to be an odd prime number.

$\ \ \ \ \$ Let $a$ and $b$ to be any integers. If $\ \ \nu_p(ab)=0 \ \$ and $\ \ 1 \leq \nu_p(a-b) \ , \$ then for every $n$ we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_p\big(a^n-b^n\big)=\nu_p\big(n(a-b)\big)=\nu_p(a-b)+\nu_p(n)$.

• Part(b) Let $p=2$.

$\ \ \ \ \$ Let $a$ and $b$ to be any integers. If $\ \ \nu_2(ab)=0 \ \$ and $\ \ 2 \leq \nu_2(a-b) \ , \$ then for every $n$ we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_2\big(a^n-b^n\big)=\nu_2\big(n(a-b)\big)=\nu_2(a-b)+\nu_2(n)$.

Lemma(2):

• Part(a) Let $p$ to be an odd prime number.

$\ \ \ \ \$ Let $a$ and $b$ to be any integers. If $\ \ \nu_p(ab)=0 \ \$ and $\ \ 1 \leq \nu_p(a+b) \ , \$ then for odd $n$ we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_p\big(a^n+b^n\big)=\nu_p\big(n(a+b)\big)=\nu_p(a+b)+\nu_p(n)$.

• Part(b) Let $p=2$.

$\ \ \ \ \$ Let $a$ and $b$ to be any integers. If $\ \ \nu_2(ab)=0 \ \$ and $\ \ 2 \leq \nu_2(a+b) \ , \$ then for odd $n$ we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_2\big(a^n+b^n\big)=\nu_2\big(n(a+b)\big)=\nu_2(a+b)+\nu_2(n)$.

Lemma(3): Let $p$ to be a prime number. Assume that the Lemma holds for $n=r$ and arbitrary $a$ & $b$. Also asssume that the Lemma holds for $n=r$ and arbitrary $a$ & $b$. then this holds for $n=rs$ and arbitrary $a$ & $b$.

Proof: Let $A:=a^r$ & $B:=b^r$.

$\nu_p\big(a^{rs}-b^{rs}\big)= \nu_p\Big((a^r)^s-(b^r)^s\Big)= \nu_p\big(A^s-B^s\big) \overset { \tiny {\text {Lemma for$n=s$} } } {=} \\ %%%%%%%%%%%%%%%%%%%%%%%%%%% %%\nu_p\big(s(A-B)\big)= %% %%%%%%%%%%%%%%%%%%%%%%%%%%% \nu_p(A-B)+\nu_p(s)= \nu_p(a^r-b^r)+\nu_p(s) \overset { \tiny {\text {Lemma for$n=r$} } } {=} \\ \big(\nu_p(a-b)+\nu_p(r)\big)+\nu_p(s)= \nu_p(a-b)+\big(\nu_p(r)+\nu_p(s)\big)= \nu_p(a-b)+\nu_p(rs)$

Lemma(4):

• Part(a) Let $p$ to be an odd prime number.

$\ \ \ \ \$ Let $a$ and $b$ to be any integers. If $\ \ \nu_p(ab)=0 \ \$ and $\ \ 1 \leq \nu_p(a-b) \ , \$ then we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_p\big(a^p-b^p\big)=\nu_p\big(p(a-b)\big)=\nu_p(a-b)+\nu_p(p)$.

Proof: Assume that $a-b=lp^{\nu}$, with $gcd(l,p)=1$ and $\nu$ is the abbreviation for $\nu_p(a-b)$. Then we have:

$\nu_p \big(a^p-b^p\big)= \nu_p \big((lp^{\nu}+b)^p-b^p\big)= \nu_p \Bigg( \sum_{i=1}^{i=p}\Big(C(i,p)(lp^{\nu})^i b^{(p-i)})\Big) \Bigg)= \nu_p \Big(C(1,p)(lp^{\nu})^1 b^{(p-1)}\Big)= \nu_p \Big( p (lp^{\nu}) b^{(p-1)}\Big)= \nu_p \Big( p . p^{\nu} \Big)= 1+\nu= \nu_p(a-b)+1= \nu_p(a-b)+\nu_p(p)$

So the assertion holds for $n=p$.

Lemma(5):

• Part(a) Let $p$ to be an odd prime number, and let $q \neq p$ to be another distinct prime number.

$\ \ \ \ \$ Let $a$ and $b$ to be any integers. If $\ \ \nu_p(ab)=0 \ \$ and $\ \ 1 \leq \nu_p(a-b) \ , \$ then we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_p\big(a^qp-b^q\big)=\nu_p\big(q(a-b)\big)=\nu_p(a-b)+\nu_p(q)$.

Proof: Assume that $a-b=lp^{\nu}$, with $gcd(l,p)=1$ and $\nu$ is the abbreviation for $\nu_p(a-b)$ . Then we have:

$\nu_p \big(a^q-b^q\big)= \nu_p \big((lp^{\nu}+b)^q-b^q\big)= \nu_p \Bigg( \sum_{i=1}^{i=q}\Big(C(i,q)(lp^{\nu})^i b^{(q-i)})\Big) \Bigg)= \nu_p \Big(C(1,q)(lp^{\nu})^1 b^{(q-1)}\Big)= \nu_p \Big( q (lp^{\nu}) b^{(q-1)}\Big)= \nu_p \Big( q p^{\nu} \Big)= \nu= \nu_p(a-b)+0= \nu_p(a-b)+\nu_p(q)$

So the assertion holds for $n=q$.

Proof of the lemma(1), Part(a). We will prove the Lemma(1) by induction on $n$. By considering the Lemma(3) it only suffices to prove the lemma for prime exponents, which already we have done in lemma(4) and lemma(5).

Proof of the lemma(2): Let $a^{\prime}=a$, $b^{\prime}=-b$. It only suffices to notice that for odd $n$ we have:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a^n+b^n=a^{\prime ^ n}-b^{\prime ^ n}$.

Now it can easily derived from lemma(1).

At first suppose that $p$ is odd, and let $x=p-1$ and $y=2p-1$.
• If $n$ is odd; then we have: $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nu_p(x^n+1)=\nu_p(x+1)+\nu_p(n)= \nu_p(y+1)+\nu_p(n)=\nu_p(y^n+1)$.
• If $n$ is even; then we have: $\ \ \ \ \ \ \ \ \ \ \ \ \ \nu_p(x^n+1)=0=\nu_p(y^n+1)$.
• At first forgive me for the mistake in the lemma. Notice that we must have: $p \nmid ab$. But in fact this condition does not restrict us, because we can factor the $p$ part. For example $\nu_5(300^{375}-50^{375})= \nu_5\big( 25^{375} ( 12^{375}-2^{375} )\big) = \\ 2*375+ \nu_5(12^{375}-2^{375})= 2*375+ \nu_5(12-2)+ \nu_5(375)$ – Davood Aug 1 '17 at 19:05