Mathematics Asked on January 3, 2022
Let $a,b,c$ belong to ${0,1,….p-1}$, where $p$ is an odd prime. We need to find the number of triplets $(a,b,c)$ such that $a^2-bc$ is divisible by $p$, but $a$ isn’t.
The solution to this problem claims that there are $(p-1)$ ways to choose $a$, $(p-1)$ ways for $b$, and for each $(a,b)$, there is one value of $c$. So, a total of $(p-1)^2$ cases.
Now the first two statements make perfect sense: $a$ can be anything except $0$, since $a$ is not divisible by $p$. $b$ cannot be zero, since then $a^2-bc=a$, which can’t be divisible by $p$. However, I have no idea why for each $(a,b)$ there will always be a value for $c$, and not more than $1$.
I tried to prove this, but couldn’t get far. I could only establish that $a^2$ can be congruent to ${1,4,9,ldots,frac{1}{4}(p-1)^2}$ mod $p$. Combining this with the fact that $b$ can be ${1,2,3,ldots,p-1}$ mod $p$, I can’t think of any reasoning that forces $c$ to take only a single value for each $(a,b)$.
If $a^2-bc$ is divisible by $p$, then $a^2-bcequiv0pmod p$, so $a^2equiv bcpmod p$.
Given $bin{1,...,p-1}$, there is a unique $tin {1,...,p-1}$ such that $btequiv1bmod p$;
$t$ is the multiplicative inverse modulo $p$ of $b$.
Then $ta^2equiv tbcequiv1cequiv cpmod p$, so $c$ is uniquely determined.
Answered by J. W. Tanner on January 3, 2022
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP