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

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP