Help understanding what this theorem means

Printable View

March 29th 2011, 04:35 PM
paupsers

Help understanding what this theorem means

Theorem. If $p$ is a prime and $(a,p)=1$ , then the congruence $x^n$ $\equiv$ $a (mod p)$ has $(n, p-1)$ solutions or no solution according as
$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.
March 29th 2011, 04:49 PM
tonio

Quote:

Originally Posted by paupsers

Theorem. If $p$ is a prime and $(a,p)=1$ , then the congruence $x^n$ $\equiv$ $a (mod p)$ has $(n, p-1)$ solutions or no solution according as
$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 $a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^*$ has n-th root there iff

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

Tonio
April 9th 2011, 12:48 AM
abhishekkgp

Quote:

Originally Posted by paupsers

Theorem. If $p$ is a prime and $(a,p)=1$ , then the congruence $x^n$ $\equiv$ $a (mod p)$ has $(n, p-1)$ solutions or no solution according as
$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 $a^{(p-1)/(n,p-1)} \equiv 1 \, (mod \, p)$ then $x^n \equiv a \,(mod \, p)$ has $gcd(n,p-1)$ solutions and if $a^{(p-1)/(n,p-1)} \neq 1 \, (mod \, p)$ then $x^n \equiv a \, (mod \, p)$ has no solutions.