TransWikia.com

Establishing divisibility by a prime

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)$.

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

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