# Help understanding what this theorem means

• Mar 29th 2011, 04:35 PM
paupsers
Help understanding what this theorem means
Theorem. If $\displaystyle p$ is a prime and $\displaystyle (a,p)=1$, then the congruence $\displaystyle x^n$ $\displaystyle \equiv$$\displaystyle a (mod p) has \displaystyle (n, p-1) solutions or no solution according as \displaystyle a^{(p-1)/(n,p-1)} \equiv 1 (mod p) or not. Can someone explain what this means linguistically? I don't understand what "according as [...] or not" means. • Mar 29th 2011, 04:49 PM tonio Quote: Originally Posted by paupsers Theorem. If \displaystyle p is a prime and \displaystyle (a,p)=1, then the congruence \displaystyle x^n \displaystyle \equiv$$\displaystyle a (mod p)$ has $\displaystyle (n, p-1)$ solutions or no solution according as
$\displaystyle a^{(p-1)/(n,p-1)} \equiv 1 (mod p)$
or not.

Can someone explain what this means linguistically? I don't understand what "according as [...] or not" means.

"An integer a coprime with a prime p is an n-th root modulo p iff a raised to the power that

appears there equals 1 mod p"

Or in the language of groups: an element $\displaystyle a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$ has n-th root there iff

its order divides $\displaystyle \frac{p-1}{(n,p-1)}$

Tonio
• Apr 9th 2011, 12:48 AM
abhishekkgp
Quote:

Originally Posted by paupsers
Theorem. If $\displaystyle p$ is a prime and $\displaystyle (a,p)=1$, then the congruence $\displaystyle x^n$ $\displaystyle \equiv$$\displaystyle a (mod p)$ has $\displaystyle (n, p-1)$ solutions or no solution according as
$\displaystyle a^{(p-1)/(n,p-1)} \equiv 1 (mod p)$
or not.

Can someone explain what this means linguistically? I don't understand what "according as [...] or not" means.

this means that if $\displaystyle a^{(p-1)/(n,p-1)} \equiv 1 \, (mod \, p)$ then $\displaystyle x^n \equiv a \,(mod \, p)$ has $\displaystyle gcd(n,p-1)$ solutions and if $\displaystyle a^{(p-1)/(n,p-1)} \neq 1 \, (mod \, p)$ then $\displaystyle x^n \equiv a \, (mod \, p)$ has no solutions.