prime number dividing $a^N+b^n+c^N$ !CMO 2015 P5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aditya21

717 posts

aditya21

#1 h Apr 24, 2015, 8:34 PM • 5 Y

Y by doxuanlong15052000, rafayaashary1, Davi-8191, Adventure10, Mango247

Let $p$ be a prime number for which $\frac{p-1}{2}$ is also prime, and let $a,b,c$ be integers not divisible by $p$ . Prove that there are at most $1+\sqrt {2p}$ positive integers $n$ such that $n<p$ and $p$ divides $a^n+b^n+c^n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cobbler

2180 posts

cobbler

#2 h Apr 25, 2015, 8:40 PM • 2 Y

Y by Delray, Adventure10

Here is the official solution: https://cms.math.ca/Competitions/CMO/solutions/sol_2015.pdf

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cobbler

2180 posts

cobbler

#4 h Apr 25, 2015, 9:30 PM • 2 Y

Y by Adventure10, Mango247

The first two primes $p$ are $p=5,7$ . Now if $p\ge 11$ we easily see that $p$ must be of the form $6k+5\equiv 2\pmod 3$ . Therefore, we can apply the lemma that $p\mid x^2+xy+y^2\equiv 0\pmod p,$ $x,y\in \mathbb{Z},$ $p\equiv 2\pmod 3$ $\Rightarrow p\mid x,y$ to get that if $p\mid a^n+b^n+c^n$ then $p\nmid a^{2n}+b^{2n}+c^{2n}$ . To see why, observe that $p\mid a^n+b^n+c^n$ $\Rightarrow c^n\equiv -(a^n+b^n)\pmod p$ ; thus $a^{2n}+b^{2n}+c^{2n}$ $\equiv a^{2n}+b^{2n}+(a^n+b^n)^2$ $\equiv 2(a^{2n}+a^nb^n+b^{2n})\pmod p$ , so if this is $\equiv 0\pmod p$ , then by the lemma we would have $p\mid a^n,b^n$ and thus $p\mid a,b$ , contradicting $p\nmid a,b,c$ .

I was wondering if this approach could be carried out to solve the problem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cobbler

2180 posts

cobbler

#6 h Apr 25, 2015, 9:38 PM • 2 Y

Y by Adventure10, Mango247

Just a note --

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JuanOrtiz

366 posts

JuanOrtiz

#7 h May 27, 2015, 12:53 AM • 4 Y

Y by rafayaashary1, Davi-8191, Adventure10, Mango247

Let $s$ be the number of $n$ that satisfy $a^n+b^n\equiv -1$ . Then for a constant $1 \le \ell \le p-2$ , if $a^n+b^n=a^{n+\ell}+b^{n+\ell}$ then $a^n(a^{\ell}-1)+b^n(b^{\ell}-1)=0$ . If $\ell \neq (p-1)/2$ this has at most two solutions $n$ . Therefore in the set of differences between $n$ that satisfy, each number appears at most twice except $(p-1)/2$ , which appears at most $s$ times. This is equivalent to $s^2-2s \le 2(p-2)$ , and by the general formula this implies $s \le \left( \frac{1}{2} \right)(2+\sqrt{4+8(p-2)}) < 1+\sqrt{2p}$ , so we are done.

This post has been edited 1 time. Last edited by JuanOrtiz, May 27, 2015, 12:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Amathlover

3 posts

Amathlover

#8 h Jul 21, 2015, 11:38 AM • 2 Y

Y by Adventure10, Mango247

JuanOrtiz wrote:

Let $s$ be the number of $n$ that satisfy $a^n+b^n\equiv -1$ . Then for a constant $1 \le \ell \le p-2$ , if $a^n+b^n=a^{n+\ell}+b^{n+\ell}$ then $a^n(a^{\ell}-1)+b^n(b^{\ell}-1)=0$ . If $\ell \neq (p-1)/2$ this has at most two solutions $n$ . Therefore in the set of differences between $n$ that satisfy, each number appears at most twice except $(p-1)/2$ , which appears at most $s$ times. This is equivalent to $s^2-2s \le 2(p-2)$ , and by the general formula this implies $s \le \left( \frac{1}{2} \right)(2+\sqrt{4+8(p-2)}) < 1+\sqrt{2p}$ , so we are done.

(I am not good at English)I have a problem, in s^2-2s every unit doublet is counted twice ,but 2(p-2) count once,what's wrong?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Amathlover

3 posts

Amathlover

#9 h Jul 21, 2015, 1:27 PM • 2 Y

Y by Adventure10, Mango247

Amathlover wrote:

JuanOrtiz wrote:

Let $s$ be the number of $n$ that satisfy $a^n+b^n\equiv -1$ . Then for a constant $1 \le \ell \le p-2$ , if $a^n+b^n=a^{n+\ell}+b^{n+\ell}$ then $a^n(a^{\ell}-1)+b^n(b^{\ell}-1)=0$ . If $\ell \neq (p-1)/2$ this has at most two solutions $n$ . Therefore in the set of differences between $n$ that satisfy, each number appears at most twice except $(p-1)/2$ , which appears at most $s$ times. This is equivalent to $s^2-2s \le 2(p-2)$ , and by the general formula this implies $s \le \left( \frac{1}{2} \right)(2+\sqrt{4+8(p-2)}) < 1+\sqrt{2p}$ , so we are done.

(I am not good at English)I have a problem, in s^2-2s every unit doublet is counted twice ,but 2(p-2) count once,what's wrong?

ok，this question is solved.according to Fermat's little threom,every |（i-j)|equal p-1-|i-j|,so we only need to consider |i-j|<p-1/2

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Amathlover

3 posts

Amathlover

#10 h Jul 21, 2015, 1:30 PM • 2 Y

Y by Adventure10, Mango247

Amathlover wrote:

JuanOrtiz wrote:

Let $s$ be the number of $n$ that satisfy $a^n+b^n\equiv -1$ . Then for a constant $1 \le \ell \le p-2$ , if $a^n+b^n=a^{n+\ell}+b^{n+\ell}$ then $a^n(a^{\ell}-1)+b^n(b^{\ell}-1)=0$ . If $\ell \neq (p-1)/2$ this has at most two solutions $n$ . Therefore in the set of differences between $n$ that satisfy, each number appears at most twice except $(p-1)/2$ , which appears at most $s$ times. This is equivalent to $s^2-2s \le 2(p-2)$ , and by the general formula this implies $s \le \left( \frac{1}{2} \right)(2+\sqrt{4+8(p-2)}) < 1+\sqrt{2p}$ , so we are done.

(I am not good at English)I have a problem, in s^2-2s every unit doublet is counted twice ,but 2(p-2) count once,what's wrong?

ok，this question is solved.according to Fermat's little theorm,every |（i-j)|equal p-1-|i-j|,so we only need to consider |i-j|<p-1/2

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MonsterS

148 posts

MonsterS

#11 h Mar 11, 2017, 5:28 PM • 2 Y

Y by Adventure10, Mango247

Any other ideas?

This post has been edited 1 time. Last edited by MonsterS, Mar 11, 2017, 5:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#12 h Sep 21, 2023, 11:17 PM • 1 Y

Y by centslordm

Let $q=\tfrac{p-1}{2}$ . By scaling WLOG assume $c=1$ . Let $S \in \mathbb{Z}/(p-1)\mathbb{Z}$ be the set of all $n$ such that $a^n+b^n \equiv -1 \pmod{p}$ . We first do some "auxillary" work. If $\mathrm{ord}_p(a/b)=1 \implies a=b$ , then we are looking for $n$ with $a^n \equiv -1/2 \pmod{p}$ . Since $p \neq 2,3$ , $-1/2 \not \in \{-1,1\} \pmod{p}$ , hence at most two $n$ work. If $\mathrm{ord}_p(a/b)=2 \implies a=-b$ , then we actually need $n$ even which yields the same equation. Hence $\mathrm{ord}_p(a/b) \in \{q,2q\}$ . The main part of the problem is the following claim.

Claim: Each difference between distinct elements of $S$ shows up at most twice, except for $q$ .
Proof: Suppose we had $k \neq l$ (in $\mathbb{Z}/(p-1)\mathbb{Z}$ ) with $k,l,k+d,l+d \in S$ for some $d \neq 0$ . Upon multiplication and cancellation this implies
$a^{l+d}b^k+a^kb^{l+d}\equiv a^{k+d}b^l+a^lb^{k+d} \pmod{p} \implies a^kb^l(a^d-b^d) \equiv a^lb^k(a^d-b^d) \pmod{p}.$ Hence either $(a/b)^d \equiv 1 \pmod{p}$ or $(a/b)^{k-l} \equiv 1 \pmod{p}$ . If $d \neq q$ , then this means $k-l=q$ , which implies the desired claim. $\blacksquare$

For any element of $S$ , there are at least $|S|-2$ other elements which don't differ from it by $q$ , hence we need $|S|(|S|-2) \leq 2(p-2)$ . Solving for $|S|$ yields the desired result. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Sep 22, 2023, 12:57 PM

Z K Y