# Thread: congruence existence problem

1. ## congruence existence problem

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$

2. 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}$.

3. what is a primitive root modulo p?

4. 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

$ab=p-1=\left|\mathbb Z_p^\times\right|=\left|f\left(\mathbb Z_p^\times\right)\right|\cdot|K|\leqslant|A|\cdot| K|\leqslant ab$

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

5. 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
$ab=p-1=\left|\mathbb Z_p^\times\right|=\left|f\left(\mathbb Z_p^\times\right)\right|\cdot|K|\leqslant|A|\cdot| K|\leqslant ab$
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).