Given a prime number $p{}$ and integers $x{}$ and $y$, find the remainder of the sum $x^0y^{p-1}+x^1y^{p-2}+\ldots+x^{p-2}y^1+x^{p-1}y^0$ upon division by $p{}$.
Problem
Source: Estonia TST 2023
Tags: number theory
03.08.2023 13:13
$\frac{x^p-y^p}{x-y} \equiv S \mod p$ if $x\equiv y \mod p$ it equal to $ 0 \equiv px^{p-1} \equiv S \mod p$ if $x \not \equiv y \mod p$ $1 \equiv S \mod p$ since $\gcd(x-y,p) = 1$ since it means that $(x-y)$ has its inverse mod p and the above $x^p -y^p$ equalizes to $(x-y)$
04.08.2023 04:18
Why it equal to $ 0 \equiv px^{p-1} \equiv S \mod p$
04.08.2023 04:35
If you let $x\equiv y\pmod p$ in the sum, every term is congruent to $x^{p-1}$, so the whole thing is $px^{p-1}$. (Or if you know a little calculus, it's related to the fact that the derivative of $x^p$ is $px^{p-1}$.)
06.08.2023 09:54
hi_how_are_u wrote: $\frac{x^p-y^p}{x-y} \equiv S \mod p$ if $x\equiv y \mod p$ it equal to $ 0 \equiv px^{p-1} \equiv S \mod p$ if $x \not \equiv y \mod p$ $1 \equiv S \mod p$ since $\gcd(x-y,p) = 1$ since it means that $(x-y)$ has its inverse mod p and the above $x^p -y^p$ equalizes to $(x-y)$ how is $1 \equiv S \mod p$?
06.08.2023 17:29
That's because $x^p\equiv x\pmod p$ and $y^p\equiv y\pmod p$ from Fermat's little theorem.
02.12.2023 01:25
$A=y^{p-1}+xy^{p-2}+\ldots+x^{p-1}=\dfrac{x^p-y^p}{x-y}$ If: $x\equiv y\mod p, \text{ so } A\equiv 0 \mod p$ If: $x\not\equiv y\mod p, \text{ so } A = \dfrac{x^p-y^p}{x-y}\equiv\dfrac{x-y}{x-y}\equiv 1\mod p$ Remark: By Little Fermat Theorem: \[a^p\equiv a \mod p\]
16.12.2024 20:30
Either $x \equiv y$ which is trivial, else reverse-factorise and use fermat
16.12.2024 21:25
The sum is just $frac{x^p-y^p}{x-y}$, therefore, we have that $\frac{x^p-y^p}{x-y}\equiv \frac{(x-y)^p}{x-y}=(x-y)^{p-1}\pmod{p}$ By Fermat's Little Theorem, if $p\nmid x-y$, then $(x-y)^{p-1}\equiv 1\pmod{p}$, and if $p\mid x-y, (x-y)^{p-1}\equiv 0\pmod{p}$