1
$\begingroup$

Can anyone help me solve this previous exam question?

enter image description here

$\endgroup$
1
$\begingroup$

Let $g$ be a primitive root mod 101. Then as $g^0,g^1,...,g^{99}$ runs through all nonzero residues modulo 101, $a$ has a solution in $(\star)$ iff there is $n$ with $a=(g^{n})^{15} = g^{15n}$. But by Fermat's Little Theorem, $g^{15n}$ has $\frac{100}{gcd(100,15)}=20$ different values mod 101. This gives the answer for a).

For b) you may show that if $a$ has a solution $x$, then $y$ is a solution to $(\star)$ iff $y=xg^{20n}$ for $n\in \Bbb Z$.

For the nontrivial direction of c) you can show similiarly to a) that there are exactly 20 solutions to $a^{20}=1$. Because of a), these must all have solutions to $(\star)$.

But in general, things get a bit easier if you start by showing that the solutions to $x^{15}=a$ have a 1:1-correspondence to those of $x^5 = b$ with $b^3=a$ by using that $x \rightarrow x^3$ is 1:1 in $(\Bbb Z / 101 \Bbb Z)^x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.