p divides (x-a)(x-b)(x-c)[(x-a)^i(x-b)^j(x-c)^k-1]

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

p divides (x-a)(x-b)(x-c)[(x-a)^i(x-b)^j(x-c)^k-1]

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: USA TST 2009 #8

The post below has been deleted. Click to close.

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

5850 posts

#1 h Jul 18, 2009, 10:44 PM • 5 Y

Y by Adventure10, jhu08, jmiao, Mango247, cubres

Fix a prime number $p > 5$ . Let $a,b,c$ be integers no two of which have their difference divisible by $p$ . Let $i,j,k$ be nonnegative integers such that $i + j + k$ is divisible by $p - 1$ . Suppose that for all integers $x$ , the quantity
$(x - a)(x - b)(x - c)[(x - a)^i(x - b)^j(x - c)^k - 1]$
is divisible by $p$ . Prove that each of $i,j,k$ must be divisible by $p - 1$ .

Kiran Kedlaya and Peter Shor.

Z K Y

The post below has been deleted. Click to close.

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

20 posts

JBrere

#2 h Jul 20, 2009, 5:34 AM • 7 Y

Y by qua96, Adventure10, jhu08, jmiao, Mango247, cubres, and 1 other user

Our Equation
$(x - a)(x - b)(x - c)[(x - a)^i(x - b)^j(x - c)^k - 1]$
is always $0 \pmod p$ .

First we may assume that $0 \le i,j,k < p-1$ because if $i,j,k$ any is greater than or equal to $p-1$ we may replace it with $i-p+1, j-p+1, k-p+1$ , still preserving the value of $i+j+k \pmod {p-1}$

Since these are each less than $p-1$ , $i+j+k < 3(p-1)$

If $i+j+k = 0$ then we are done. Assume for sake of contradiction they are not.

If $i+j+k = 2(p-1)$ we substitute $p-1-i, p-1-j, p-1-k$ for $i,j,k$ and since this is the inverse of the previous expression $\pmod p$ , which is always $1 \pmod p$ for all $x \ne a,b,c$ , the whole polynomial is still $0 \pmod p$ for all integers.

So we can assume $i+j+k = p-1$ . Also since the equation is cyclic assume $i \ge j, i \ge k$ and therefore $i \ge {(p-1) \over 3}$

Also assume $p>7$ , we have
$(x - a)(x - b)(x - c)[(x - a)^i(x - b)^j(x - c)^k - 1]$

$= (x - a)(x - b)(x - c)[(x - a)^i(x - b)^j(x - c)^k - (x-a)^{p-1}]$

$= (x - a)(x - b)(x - c)[(x-b)^j(x-c)^k - (x-a)^{j+k}]$
(We can divide out by all the repeated roots because the polynomial remains $0 \pmod p$ for all integers.)

Now this polynomial has degree $\le {2p+7 \over 3}$ which for all $p>7$ is less than $p$ thus this polynomial (which is clearly not the 0 polynomial since $a,b,c$ are distinct) has less than $p$ roots $\pmod p$ thus it is not $0 \pmod p$ for all integers $x$ .

For the $p=7$ case the above argument holds for all cases except $i=j=k=2$ .
then we have $(x-a)(x-b)(x-c)[(x-b)^2(x-c)^2-(x-a)^4]$ Since the $x^4$ term within the brackets vanishes the polynomial is of degree 6, and is clearly not the zero polynomial $\pmod 7$ . Contradiction

Z K Y

The post below has been deleted. Click to close.

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

Ahwingsecretagent

151 posts

Ahwingsecretagent

#3 h Jul 21, 2009, 6:28 AM • 5 Y

Y by Adventure10, jhu08, jmiao, Mango247, cubres

Wonderful solution! Thank you. I was trying to use primitive roots which failed.

Z K Y

The post below has been deleted. Click to close.

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

anonymouslonely

1142 posts

anonymouslonely

#4 h Mar 11, 2013, 5:10 PM • 6 Y

Y by Adventure10, jhu08, jmiao, Mango247, cubres, and 1 other user

in the field $Z_{p}$ is still true that if $f$ has a double root $r$ then $f'(r)=0$ ?

Z K Y

The post below has been deleted. Click to close.

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

139 posts

goo

#5 h Mar 14, 2013, 12:38 AM • 4 Y

Y by Adventure10, jhu08, Mango247, cubres

anonymouslonely wrote:

in the field $Z_{p}$ is still true that if $f$ has a double root $r$ then $f'(r)=0$ ?

Yes, this is true. It follows easily from the fact that the product-rule for derivatives works the same in $Z_p[x]$ as it works in $\mathbb{R}[x]$ .

Z K Y

The post below has been deleted. Click to close.

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

1479 posts

#6 h Apr 30, 2013, 7:12 AM • 4 Y

Y by Adventure10, jhu08, cubres, and 1 other user

Suppose $f(x)=(x-a)(x-b)(x-c)[(x-a)^i(x-b)^j(x-c)^k-1]$ .Now putting $x=1,2,.....,p$ and calling $(t-a)\equiv a_t(mod p)$ and $(t-b)\equiv b_t (mod p)$ also $(t-c)\equiv c_t (mod p)$ we obtain $p|(a_t)(b_t)(c_t)[(a_t)^i(b_t)^j(c_t)^k-1]$ where $\{a_t\}=\{b_t\}=\{c_t\}=\{1,2,3,.....,p\}$ . Now suppose $\{1,2,3,....,p\}=\{g^{a_1},g^{a_2},........,g^{a_p}\} (mod p)$ . Also call $a_t \equiv g^{f_{1}(t)}(mod p )$ also $b_t\equiv g^{f_{2}(t)}(mod p )$ and $c_t\equiv g^{f_{3}(t)}(mod p )$ for all $1\leq t\leq p$ .Now certainly we're getting $p-1|if_{1}(t)+jf_{2}(t)+kf_{3}(t)$ for all such $t$ .Now $WOLG$ assume $i\geq j\geq k$ . Also note as we've $i+j\equiv -k (mod (p-1))$ so we get $p-1|mf_{2}(t)+nf_{3}(t)$ for all such $t$ with $m=i-j,n=i-k$ . Now consider a mapping where if $f_{2}(t)=h$ then $f_{3}(t)=X(h)$ for all $1\leq h\leq p$ . Thus now for all $h$ we've $p-1|hx+yX(h)$ . Now so we've if $p-1$ doesn't divide $y$ then $p-1|(k-1)X(k)-kX(k-1)$ also so, $p-1|X_{p-1}-(p-1)X(1)$ .Now basically just summing we obtain $\frac{p(p-1)}{2}-Xp\equiv \frac{p(p-1)}{2} X(1) (mod p)$ and so $p|Xp$ .Now note $p-1|pX_{p-1}-p(p-1)$ and obviously so $X_{p-1}=p-1$ . Now similarly going on we get $X_{i}=i$ for all $1\leq i\leq p$ if our $y$ is not divisible by $p$ .Now as $p>5$ so we can chose a odd prime $q<p$ .Now so we've $p-1|q(x+y)$ but that implies $p-1|x+y$ since $q$ is odd and $gcd(p-1,q)=1$ . And hence $p-1|i+j-2k$ also we've $p-1|i+j+k$ and so finally we get $p-1$ divides all of $i,j,k$ .

Z K Y

The post below has been deleted. Click to close.

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

1980 posts

#7 h Aug 13, 2016, 5:47 PM • 3 Y

Y by Adventure10, jhu08, cubres

Solution. By Fermat's Little Theorem (from here one, we will call it FLT) we see that only considering the residue classes of $i,j,k$ modulo $p-1$ doesn't affect the congruence. Thus, we may assume that $i,j,k$ are in the set $\{0,1,\dots, p-2\}$ . Now, $i+j+k < 3(p-1)$ and so the only possible cases are $i+j+k \in \{0,p-1,2(p-1)\}$ . In the case when the sum vanishes, we are done. If the sum is $2(p-1)$ , we can consider the triple obtained by removing $i,j,k$ from $p-1$ (ensured by FLT). In any case, we may assume that $i+j+k=p-1$ . Now the congruence equation $\begin{align*} (x-a)^i(x-b)^j(x-c)^k=1 \end{align*}$ is given to have $p-3$ solutions in the domain $F_p[X]$ . Assume that $i$ is the largest of the three exponents. This, by the FLT, boils down to the equation $\begin{align*} (x-b)^j(x-c)^k-(x-a)^{j+k} =0 \end{align*}$ having $p-3$ solutions. This equation is not an identity (distinct variables etc) and has degree at most $j+k-1 \le \frac{2(p-1)}{3}-1$ (leading coefficient vanishes). However, by Lagrange's theorem, this shows that $p-3 \le \frac{2(p-1)}{3}-1$ , which clearly fails for $p \ge 7$ . The result follows.

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#8 h Oct 19, 2017, 9:34 AM • 4 Y

Y by tenplusten, Adventure10, jhu08, cubres

When you forgot Lagrange's Theorem.

Crazy Solution

This post has been edited 1 time. Last edited by MarkBcc168, Oct 19, 2017, 9:36 AM

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#9 h Feb 18, 2019, 5:56 AM • 5 Y

Y by pavel kozlov, Adventure10, jhu08, Mango247, cubres

bad solution:

Removing the fluff, what we are given is that
$(x-a)^i(x-b)^j(x-c)^k\equiv 1\pmod{p}$ for all $x\in\mathbb{F}_p\setminus\{a,b,c\}$ . Also, we might as well take the $i,j,k$ mod $p-1$ because of Fermat's little theorem. Furthermore, we may send $(i,j,k)\to(-i,-j,-k)$ if we wish to becauase $1^{-1}\equiv 1\pmod{p}$ .

By taking mod $p-1$ , we may assume WLOG that $0\le i\le j\le k\le p-2$ . We see that $i+j+k=0,p-1,2(p-1)$ since $p-1\mid i+j+k$ . If $i+j+k=0$ , we're actually done, so for sake of contradiction, suppose not. Now, if $i+j+k=2(p-1)$ , then send $(i,j,k)\to(p-1-k,p-1-j,p-1-i)\pmod{p-1}$ . So potentially re-ordering again, we may assume $0\le i\le j\le k\le p-2$ , and $i+j+k=p-1$ . Finally, send $k\to k-(p-1)$ , so now we have $0\le|i|,|j|,|k|\le p-2$ , $i,j\ge 0$ , and $-k=i+j$ .

Thus, we have
$(x-a)^i(x-b)^j\equiv(x-c)^{i+j}\pmod{p}$ for all $x\not\equiv a,b,c\pmod{p}$ . Let $P(x)=(x-a)^i(x-b)^j-(x-c)^{i+j}$ .By letting $x=a$ , we see that this polynomial is not identically $0$ (here we are working over $\mathbb{F}_p$ ). Thus, $1\le\deg P\le k-1$ , but $P(x)$ has $p-3$ roots (which are $\mathbb{F}_p\setminus\{a,b,c\}$ ). Therefore, $P(x)$ factors into $p-3$ linear factors, so in fact $p-3\le k-1$ . But $k-1\le p-3$ , so in fact $p-3=k-1$ , so $k=p-2$ . It is not hard to see that this means
$(x-a)^i(x-b)^{1-i}(x-c)^{-1}\equiv 1\pmod{p}$ for all $x\not\equiv a,b,c\pmod{p}$ . Thus, $(x-a)^i-(x-b)^{i-1}(x-c)\equiv 0\pmod{p}$ for all $x\not\equiv a,b,c\pmod{p}$ , so by similar logic to above, we have $i-1\ge p-3$ , so $i=p-2$ as well.

So we have $i=k=-1$ , so $j=2$ . Thus,
$(x-b)^2\equiv (x-a)(x-c)\pmod{p}$ for all $x\not\equiv a,b,c\pmod{p}$ , so $-2bx+b^2\equiv -(a+c)x+ac\pmod{p}$ for those same $x$ values. If $p>5$ , we must then have that $2b\equiv a+c\pmod{p}$ and $b^2\equiv ac\pmod{p}$ . Therefore,
$(a-c)^2=(a+c)^2-4ac\equiv 4b^2-4b^2\equiv 0\pmod{p},$ so $a\equiv c\pmod{p}$ , which is the desired contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1207 posts

#10 h Apr 13, 2019, 12:15 AM • 4 Y

Y by Adventure10, jhu08, Mango247, cubres

Here's a cleaner finish than using Lagrange.

First we may assume that $i, j, k < p-1$ by FLT, so $i+j+k\in \{0, p-1, 2(p-1)\}$ .

If $i+j+k = 0$ , we're done.
If $i+j+k = 2(p-1)$ , send $i\to (p-1)-i$ (and similarly for $j$ and $k$ ) so that $i+j+k=p-1$ . This does not affect the hypothesis by FLT.

Hence we can assume $i+j+k=p-1$ . Let
$f(x) = (x-a)^i(x-b)^j(x-c)^k - 1,$ so by hypothesis $f$ vanishes everywhere except at $a, b, c$ . This implies $\sum_{x=0}^{p-1} f(x) \equiv -3\pmod p$ .

However, $f$ is monic with degree $p-1$ , and thus $\sum_{x=0}^{p-1} f(x) \equiv -1\pmod p$ , contradiction.

Here are the details for the last step. If we let $g = f-x^{p-1}$ have degree less than $p-1$ , we can write
$\sum_{x=0}^{p-1} f(x) = \sum_{x=0}^{p-1} x^{p-1} + \sum_{x=0}^{p-1} g(x) \equiv -1\pmod p,$ where we are using the fact that if a polynomial $P$ has degree less than $p-1$ , then $\sum_x P(x) \equiv 0\pmod p$ . Of course this follows from the fact that
$1^k+2^k+\dots +(p-1)^k\equiv 0\pmod p$ if $p-1\nmid k$ .

Z K Y

The post below has been deleted. Click to close.

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

1218 posts

#11 h Apr 13, 2019, 7:40 AM • 4 Y

Y by Adventure10, jhu08, Mango247, cubres

Nice problem! The idea involved is truly magnificent. Here's my solution: If $i \geq p-1$ , then replace $i \rightarrow i-(p-1)$ , and note that the given condition remains invariant due to Fermat's Little Theorem. So WLOG assume that $0 \leq i,j,k \leq p-2$ (from now on we will take $i,j,k$ modulo $p-1$ ). Then we have $i+j+k=0,p-1,2(p-1)$ . If $i+j+k=0$ , then we must have $i,j,k=0$ , which is what we needed. If $i+j+k=2(p-1)$ , then replace $i \rightarrow p-1-i$ , and similarly for others, to get the same condition (again with the help of FLT). So we can assume that $i+j+k=p-1$ and $0 \leq i,j,k \leq p-2$ .

Now, the given condition is equivalent to saying that $(x-a)^i(x-b)^j(x-c)^k \equiv 1 \pmod{p} \text{ } \forall x \in \mathbb{F}_p \setminus \{a,b,c\}$ $\Rightarrow (x-a)^i(x-b)^j \equiv (x-c)^{i+j} \pmod{p} \text{ } \forall x \in \mathbb{F}_p \setminus \{a,b,c\}$ where we use FLT along with the fact that $k=(p-1)-(i+j)$ . This means that the polynomial $G(x)=(x-a)^i(x-b)^j-(x-c)^{i+j}$ has $p-3$ roots (where we have $G \in \mathbb F_p[x]$ ). As degree of $G$ is at most $i+j-1$ , so we have $i+j-1 \geq p-3 \Rightarrow p-2-k \geq p-3 \Rightarrow k \leq 1 \Rightarrow k=0,1$ Now we have the following two cases to deal with:-

If $k=0$ , then we have $(x-a)^i(x-b)^j \equiv 1 \pmod{p} \Rightarrow (x-a)^i(x-b)^{p-1-i} \equiv 1 \pmod{p}$ Multiplying both sides of the congruence by $(x-b)^i$ , and with the help of FLT, we get that $(x-a)^i \equiv (x-b)^i \pmod{p}$ . Again consider the polynomial $H(x)=(x-a)^i-(x-b)^i$ , which has $p-3$ roots in $\mathbb F_p[x]$ . As $\text{deg}(H) \leq i-1$ , so $i-1 \geq p-3$ , which gives $i=p-2$ (since $0 \leq i \leq p-2$ ). But then, working in $\mathbb F_p,$ we have $(x-a)^{p-2}=(x-b)^{p-2} \Rightarrow (x-a)^{p-1}(x-b)=(x-b)^{p-1}(x-a) \Rightarrow x-b=x-a \Rightarrow a=b \Rightarrow p \mid a-b \rightarrow \text{CONTRADICTION}$ $\text{ }$
Let $k=1$ . Then we have $j=p-2-i$ , which gives $(x-a)^i(x-b)^{p-2-i}(x-c) \equiv 1 \pmod{p} \Rightarrow (x-a)^i(x-c) \equiv (x-b)^{i+1} \pmod{p}$ Let $T(x)=(x-a)^i(x-c)-(x-b)^{i+1}$ be a polynomial in $\mathbb F_p[x]$ . Then, it has $p-3$ roots, and $\text{deg}(T) \leq i$ . This gives $i \geq p-3$ , which means that $i=p-3,p-2$ (since $0 \leq i \leq p-2$ ). If $i=p-2$ , then $j=0$ , in which case we can arrive at a contradiction in a similar manner as we did for the case $k=0$ . So we must have $i=p-3,j=k=1$ . This gives $(x-a)^{p-3}(x-b)(x-c) \equiv 1 \pmod{p} \Rightarrow (x-b)(x-c) \equiv (x-a)^2 \pmod{p} \text{ } \forall x \in \mathbb{F}_p \setminus \{a,b,c\}$ where we multiply both sides by $(x-a)^2$ and use FLT. As this has $p-3$ roots, and $p-3>1$ (since $p>5$ ), so the identity $(x-a)^2=(x-b)(x-c)$ should be true in $\mathbb F_p$ . Thus, we have (working in $\mathbb F_p$ ) $b+c=2a \text{ and } bc=a^2$ . As this is the equality case of the AM-GM inequality, so we must have $b=c$ , which contradicts the fact that $p \nmid b-c$ .

Thus, we arrive at a contradiction in all cases, as desired. $\blacksquare$

EDIT: I forgot to mention that each of the polynomials $G,H,T$ are not identities (which we get on plugging in $a,b,c$ in them). We need this since otherwise we can not apply bounding on their degrees.

This post has been edited 2 times. Last edited by math_pi_rate, Apr 13, 2019, 7:43 AM

Z K Y

The post below has been deleted. Click to close.

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

54 posts

#12 h Dec 13, 2020, 3:10 AM • 3 Y

Y by Adventure10, jhu08, cubres

pinetree1 wrote:

Here's a cleaner finish than using Lagrange.

First we may assume that $i, j, k < p-1$ by FLT, so $i+j+k\in \{0, p-1, 2(p-1)\}$ .

If $i+j+k = 0$ , we're done.
If $i+j+k = 2(p-1)$ , send $i\to (p-1)-i$ (and similarly for $j$ and $k$ ) so that $i+j+k=p-1$ . This does not affect the hypothesis by FLT.

Hence we can assume $i+j+k=p-1$ . Let
$f(x) = (x-a)^i(x-b)^j(x-c)^k - 1,$ so by hypothesis $f$ vanishes everywhere except at $a, b, c$ . This implies $\sum_{x=0}^{p-1} f(x) \equiv -3\pmod p$ .

However, $f$ is monic with degree $p-1$ , and thus $\sum_{x=0}^{p-1} f(x) \equiv -1\pmod p$ , contradiction.

Here are the details for the last step. If we let $g = f-x^{p-1}$ have degree less than $p-1$ , we can write
$\sum_{x=0}^{p-1} f(x) = \sum_{x=0}^{p-1} x^{p-1} + \sum_{x=0}^{p-1} g(x) \equiv -1\pmod p,$ where we are using the fact that if a polynomial $P$ has degree less than $p-1$ , then $\sum_x P(x) \equiv 0\pmod p$ . Of course this follows from the fact that
$1^k+2^k+\dots +(p-1)^k\equiv 0\pmod p$ if $p-1\nmid k$ .

You miss the point that $i, j, k$ might be 0, then your claim failed.

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1521 posts

GeronimoStilton

#13 h Feb 21, 2021, 1:32 PM • 3 Y

Y by Adventure10, jhu08, cubres

Reduce $i,j,k$ modulo $p-1$ . If $i+j+k=0$ we are done, and if $i+j+k=2(p-1)$ replace each with $p-1-i,p-1-j,p-1-k$ so we can WLOG assume $i+j+k=p-1$ . WLOG $i+j\le 2(p-1)/3$ . Clearly $i+j>0$ because otherwise $k$ wasn't reduced. The goal is to show we cannot have
$(x-c)^{i+j}-(x-a)^i(x-b)^j\equiv 0\pmod{p}$ for all $x\not\equiv a,b,c\pmod{p}$ . Suppose otherwise. The polynomial has degree at most $i+j-1$ but $p-3$ roots. Note it cannot be zero because then taking $x=c$ yields a contradiction. Otherwise, we get
$p-3\le i+j-1\le 2(p-1)/3-1\iff p-2\le 2(p-1)/3\iff 3p-6\le 2p-2\iff p\le 4,$ which is absurd, thus we are done.

Z K Y

The post below has been deleted. Click to close.

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

2811 posts

#14 h Aug 6, 2021, 4:16 PM • 2 Y

Y by jhu08, cubres

Interesting.

Notice by FLT, we can immediately restrict the values of $i,j,k$ to $\{0,1,...,p-2\}$ . Hence we have that $i+j+k \le 3(p-2)$ , so $i+j+k \in \{0,p-1,2(p-1)\}$ .If $i+j+k = 0$ , then it is easy to see that we are done. Now we will show that we can reduce the case where $i+j+k = 2(p-1)$ to $i+j+k= p-1$ . We can consider two cases now, one where $\max{(i,j,k)} \ge p-1$ and one where $p-1 \ge \max{(i,j,k)} \ge \frac{2(p-1)}{3}$ . In the former case, we are able to replace $\max{(i,j,k)}$ with $\max{(i,j,k)} - (p-1)$ , and in the latter case replace $\max{(i,j,k)}$ with $(p-1) - \max{(i,j,k)}$ . Now we can turn all our attention to the case where $i+j+k = p-1$ .

Observe that we are essentially operating on $\mathbb{F}_p \setminus \{a,b,c\}$ and have that ${(x-a)}^i{(x-b)}^j{(x-c)}^k = 1$ . We desire to show that this isn't possible unless $x=a,b,c$ , and we will suppose the contrary. Assume that $\max{(i,j,k)}=i$ . Applying FLT once more gives us ${(x-b)}^j{(x-c)}^k - {(x-a)}^{j+k} = 0$ , and notice that the leading degree cancels out so the degree of this polynomial is given to be $j+k-1$ . Since we have that $\max{(i,j,k)}=i$ , we get that $j+k-1 \le \frac{2(p-1)}{3}$ . By Lagrange, we have that $p-3 \le \frac{2(p-1)}{3}$ , which only holds for $p \le 4$ , ridiculous. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#15 h Aug 25, 2021, 6:47 AM • 1 Y

Y by cubres

Reduce $i,j,k$ modulo $p-1$ .
Since the equation is symmetric we can assume that $i>j>k$ (if they were equal then $p-1|i+j+k=3i=3j=3k$ or $p-1|i,p-1|j,p-1|k$ ,which is what we wanted)
If $i+j+k=0$ ,we will be done so consider the case $i+j+k=2(p-1)$ where we can replace each of $i,j,k$ with $p-i-1,p-j-1,p-k-1$ so we just need to check the case when $i+j+k=p-1$
By FLT, ${(x - a)(x - b)(x - c)[(x-b)}^j{(x-c)}^k - {(x-a)}^{j+k}] \equiv 0 \pmod p$ ,and since this works for all $x$ ,choose $x$ such that $(x - a)(x - b)(x - c) \equiv r>0 \pmod p$
By Lagrange's theorem and since $p$ is a prime, $f(X) \equiv 0 \pmod p$ ,has atmost $deg(f)>0$ solutions so $(X-b)^j(X-c)^k \equiv (X-a)^{j+k} \pmod p$ must have atleast $p$ solutions $\pmod p$ which covers all residues so it must work for all integers.
Now plugging in $X=b$ and $X=c$ gives $(b-a)^{j+k}$ and $(c-a)^{j+k}$ to be divisible by $p$
Since $p \nmid(b-a),(c-a)$ , $j+k=(p-1)r$ ,a contradiction since $0<j+k<p-1$ ,or all of $i,j,k \equiv 0 \pmod p$ ,as required.

This post has been edited 4 times. Last edited by Sprites, Aug 25, 2021, 7:03 AM

Z K Y

The post below has been deleted. Click to close.

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

8857 posts

#16 h Apr 13, 2023, 11:33 PM • 1 Y

Y by cubres

Assume that $i, j, k < p-1$ . We will show that $i=j=k=0$ .

Assume otherwise. Then $i+j+k = (p-1)$ or $2(p-1)$ ; in the former case, replace each $i$ with $p-1-i$ , so it suffices to show the former case.

WLOG $i>j>k$ . We have the reduction $(x-a)^{j+k}(x-b)(x-c) \equiv (x-b)^{j+1}(x-c)^{k+1}$ for all integers $x$ by Fermat's little theorem. But now, the relevant degree of the polynomial is $j+k+2 < p$ , hence $f \equiv 0 \pmod p$ by Lagrange. Then $(X-b)^j(X-c)^k \equiv (X-a)^{j+k} \pmod p.$ At $X=b$ , this implies $a=b$ , impossible. Thus $i=j=k=0$ .

This post has been edited 1 time. Last edited by HamstPan38825, Apr 13, 2023, 11:33 PM

Z K Y

The post below has been deleted. Click to close.

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

1324 posts

#17 h Jul 27, 2024, 10:59 PM • 1 Y

Y by cubres

WLOG $0 \leq i, j, k \leq p-2$ since we can remove $p-1$ from each of $i$ , $j$ , $k$ repeatedly since it does not affect the quantity in question. If $0 = i = j = k$ we are done so FTSOC assume this is not true.
Then $i + j + k < 3(p-1)$ so either $i + j + k = p-1$ or $2p - 1$ . If $i + j + k = 2p - 1$ then replace each of $i, j, k$ with $(p-1) - i, (p-1) - j, (p-1) - k$ to get that $i + j + k = p-1$ which is the only case we will be dealing with. Note that $1^k + 2^k + \dots + (p-1)^k \equiv 0\pmod{p}$ unless $p - 1 \mid k$ .
Then we can count $\sum_{i=1}^{p-1} (x-a)^i(x-b)^j(x-c)^k \pmod{p}$ from our previous claim as $-1 \pmod{p}$ . However since $(x-a)^i(x-b)^j(x-c)^k - 1$ vanishes modulo $p$ for all $x \neq a, b, c$ we have that $\sum_{i=1}^{p-1} (x-a)^i(x-b)^j(x-c)^k \equiv p-3 \pmod{p}$ . This is a contradiction as $p-1 \equiv p-3 \pmod{p}$ implies $p = 2$ , contradiction. So then $i \equiv j \equiv k \equiv 0\pmod{p-1}$ .

Z K Y

The post below has been deleted. Click to close.

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

1328 posts

#18 h Jan 15, 2025, 5:59 AM • 1 Y

Y by cubres

Storage:

Removing the cover; we have: for all $x \in \mathbb F_p /\{a, b, c\}$ : $(x-a)^i (x-b)^j (x-c)^k \equiv 1 \equiv (x-a)^{i+j+k} \pmod p$ Assume that: $i, j, k \le p-1$ . If $i+j+k=0$ , we are done. If $i+j+k=2(p-1)$ , replace $i$ with $p-1-i$ , $j$ with $p-1-j$ , $k$ with $p-1-k$ . Thus assume $i+j+k=(p-1)$ .

WLOG $i \ge j \ge k$ . Thus: $j+k \le \frac{2(p-1)}{3}$ . Note that: $(x-b)^j (x-c)^k \equiv (x-a)^{j+k} \pmod p$ has $p-3$ solutions. Thus, by Lagrange's Theorem we must have: $p-3 \le \frac{2(p-1)}{3}$ which leads to contradiction as $p>5$ .

Z K Y

The post below has been deleted. Click to close.

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

1729 posts

OronSH

#19 h Jan 20, 2025, 2:23 AM • 2 Y

Y by dolphinday, cubres

Shift $i,j,k$ by $p-1$ to be $<p-1$ , then if $i+j+k=2p-2$ consider $p-1-i,p-1-j,p-1-k$ instead. If $i+j+k=p-1$ then $(x-a)^i(x-b)^j(x-c)^k$ is zero on $a,b,c$ and one otherwise, but so is $(x-a)^{p-1}+(x-b)^{p-1}+(x-c)^{p-1}-2$ . Now they have the same degree and different leading term, so their difference is a polynomial of degree $p-1$ with $p$ roots $0,1,\dots,p-1$ , impossible. Thus $i+j+k=0$ so $i,j,k=0$ which implies $p-1\mid i,j,k$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

117 posts

cubres

#20 h Mar 2, 2025, 11:26 AM

Y by

Rough sketch of the solution

Z K Y

The post below has been deleted. Click to close.

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

754 posts

#21 h Mar 6, 2025, 5:44 PM • 2 Y

Y by OronSH, cubres

Subjective Rating (MOHs)
Please contact westskigamer@gmail.com if there is an error with any of my solution for cash bounties by 3/18/2025.
Bounty claims likely here since I didn't use $p > 5$ .

Attachments:

This post has been edited 1 time. Last edited by Mathandski, Mar 6, 2025, 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.

609 posts

#22 h Apr 14, 2025, 5:30 PM

Y by

We may assume $i + j + k \leq 3(p - 1).$ If $i + j + k = 3(p - 1),$ at least one is geq than $p - 1.$ Then, FLT finishes.

If $i + j + k = 2(p - 1),$ then taking $i\mapsto p - 1 - i, j\mapsto p- 1 - j, k \mapsto p - 1 - k$ implies it suffices to show the case when $i + j + k = p - 1.$

Suppose $k \leq j \leq i.$ Then, $i = p - 1 - j - k,$ so $(x - b)^j(x - c)^k \equiv (x- a)^{j + k}\pmod{p}.$ The polynomial $(x - b)^j(x - c )^k - (x - a)^{j + k}$ has $p - 3$ distinct 0s in $\mathbb F_p.$ However, the degree is bounded above by $\frac{2(p - 1)}{3} - 1.$ Since $\frac{2(p - 1)}{3} - 1 < p - 3$ is true for all $p \geq7,$ we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a