congruence existence problem

**siegfried** · April 3rd 2009, 01:22 AM

let p be a prime and suppose $p-1=ab$ for some integers a and b

prove that if $y^a\equiv1\pmod p$ there exists x such that $y\equiv x^b\pmod p$

**ThePerfectHacker** · April 3rd 2009, 11:19 AM

Originally Posted by siegfried

let p be a prime and suppose $p-1=ab$ for some integers a and b

prove that if $y^a\equiv1\pmod p$ there exists x such that $y\equiv x^b\pmod p$

Let $z$ be a primitive root modulo $p$ (we know it exists).
This means $y\equiv z^c(\bmod p)$ for some $1\leq c \leq p-1$ .
Since $y^a\equiv 1(\bmod p) \implies (z^c)^a\equiv 1(\bmod p) \implies z^{ac} \equiv 1(\bmod p)$ .
Therefore, $p-1$ divides $ac$ , thus $ab|ac \implies b|c$ .
Therefore, $y\equiv z^c = \left( z^{c/b} \right)^b = x^b(\bmod p)$ where $x=z^{c/b}$ .

**siegfried** · April 10th 2009, 10:59 AM

what is a primitive root modulo p?

**JaneBennet** · April 10th 2009, 01:19 PM

Here’s another proof.

Notice that $A=\{y\in\mathbb Z_P^\times:y^a=1\}$ is a subgroup of $\mathbb Z_p^\times=\{1,2,\ldots,p-1\}$ under multiplication modulo $p.$

Define a mapping $f:\mathbb Z_p^\times\to A$ by $f(x)=x^b.$ This makes sense because $\forall x\in\mathbb Z_p^\times,$ $(x^b)^a=x^{p-1}=1$ by Fermat’s little theorem, so that $x^b\in A.$

$f$ is clearly a homomorphism and so its image is a subgroup of $A.$ $\therefore\ \left|f\left(\mathbb Z_p^\times\right)\right|\leqslant|A|.$

Now $A$ consists of roots of the polynomial $x^a-1$ of degree $a$ in $\mathbb Z_p^\times[x],$ and there cannot be more than $a$ such roots. $\therefore\ |A|\leqslant a$ .

Similarly, the kernel of $f,$ $K=\{x\in\mathbb Z_p^\times:x^b=1\}$ consists of roots of the polynomial $x^b-1$ of degree $b$ in $\mathbb Z_p^\times[x],$ and so $|K|\leqslant b$ .

Now, by the homomorphism theorem, we have $\mathbb Z_p^\times/K\cong f\left(\mathbb Z_p^\times\right)$ . And so we have

Therefore we actually have $\left|f\left(\mathbb Z_p^\times\right)\right|=|A|,$ i.e. $f$ is surjective. This proves the theorem.

**NonCommAlg** · April 10th 2009, 01:48 PM

Originally Posted by JaneBennet

Here’s another proof.

Notice that $A=\{y\in\mathbb Z_P^\times:y^a=1\}$ is a subgroup of $\mathbb Z_p^\times=\{1,2,\ldots,p-1\}$ under multiplication modulo $p.$

Define a mapping $f:\mathbb Z_p^\times\to A$ by $f(x)=x^b.$ This makes sense because $\forall x\in\mathbb Z_p^\times,$ $(x^b)^a=x^{p-1}=1$ by Fermat’s little theorem, so that $x^b\in A.$

$f$ is clearly a homomorphism and so its image is a subgroup of $A.$ $\therefore\ \left|f\left(\mathbb Z_p^\times\right)\right|\leqslant|A|.$

Now $A$ consists of roots of the polynomial $x^a-1$ of degree $a$ in $\mathbb Z_p^\times[x],$ and there cannot be more than $a$ such roots. $\therefore\ |A|\leqslant a$ .

Similarly, the kernel of $f,$ $K=\{x\in\mathbb Z_p^\times:x^b=1\}$ consists of roots of the polynomial $x^b-1$ of degree $b$ in $\mathbb Z_p^\times[x],$ and so $|K|\leqslant b$ .

Now, by the homomorphism theorem, we have $\mathbb Z_p^\times/K\cong f\left(\mathbb Z_p^\times\right)$ . And so we have

Therefore we actually have $\left|f\left(\mathbb Z_p^\times\right)\right|=|A|,$ i.e. $f$ is surjective. This proves the theorem.

this is a pretty solution!

it shows you've got to be creative if you insist on not using standard facts

(here the one that ThePerfectHacker used, i.e. $\mathbb{Z}_p^{\times}$ is a cyclic group).

Thread: congruence existence problem

LinkBack

Thread Tools

Display

congruence existence problem

Similar Math Help Forum Discussions

Perfect Cuboid Problem: Existence Proof

Existence of a solution; Initial value problem

Problem regarding appliation of Existence & Uniqueness theorem

Problem with a limit's existence...

Another congruence problem

Search Tags