5
$\begingroup$

Let $5$ be a primitive root of $97$ and $\text{ind}_5 (45)=45$ find the number of solutions of $x^k\equiv 45\pmod{97}$ where $k=7,8,9$

My attempt:

$$5^{45}\equiv 45 \pmod{97}$$

For $k=7:$

$$x^7\equiv 45\pmod{97}$$

$$\text{ind}_5x^7=7\cdot\text{ind}_5x\equiv45 \pmod{\phi(97)}$$

$$7\cdot\text{ind}_5x\equiv45 \pmod{96}$$

$$\text{ind}_5x\equiv75 \pmod{96}$$

I am stuck here

$\endgroup$
2
  • $\begingroup$ What is $\text{ind}_m (n)$? $\endgroup$
    – Alex M.
    Jun 7, 2016 at 12:56
  • $\begingroup$ same as $\log_m n$ e.g $\text{ind}_5 (45)=45$ because $5^{45}=45$ @AlexM. $\endgroup$
    – Error 404
    Jun 7, 2016 at 12:58

2 Answers 2

4
$\begingroup$

If $G$ is a cyclic group of order $n$, then the map $x \mapsto x^k$ is $d$-to-$1$, where $d=\gcd(k,n)$ because its kernel has order $d$. In other words, if $x^k=g$ has a solution, then it has $d$ solutions.

In your case, $G=U(97)$ and $n=\phi(97)=96$. So

  • exactly $1$ solution for $k=7$.

  • at most $8$ solutions for $k=8$.

  • at most $3$ solutions for $k=9$.

The index calculus you mention works for deciding whether there are any solutions.

  • $7 j \equiv 45 \bmod 96$ has a solution because $\gcd(7,96)=1$ divides $45$.

  • $8 j \equiv 45 \bmod 96$ does not have a solution because $\gcd(8,96)=8$ does not divide $45$.

  • $9 j \equiv 45 \bmod 96$ has a solution because $\gcd(9,96)=3$ divides $45$.

You have found the solution $j=75$ for $k=7$ and so $x=5^{75} \equiv 63 \bmod 97$.

For $k=9$, you need to solve $3 j \equiv 15 \bmod 32$, which gives $j \equiv 5 \bmod 32$.

$\endgroup$
0
2
$\begingroup$

For a given integers $a,b,m$ let $d=\gcd(a,m)$. Generally, the number of solutions of $ax\equiv b(\text{mod}\,m)$ is $0$ if $d\nmid b$ or $d$ if $d\mid b$.

In your case, the congruence is equivalent to the following linear congruence: $$ k\cdot\text{ind}_5x\equiv 45(\text{mod}\,96) $$ Hence, the number of solutions is $\gcd(k,96)$ if $\gcd(k,96)\mid 45$ or $0$ if $\gcd(k,96)\nmid 45$.

$\endgroup$
1
  • $\begingroup$ the given congruence is equivalent to a linear congruence $\endgroup$
    – boaz
    Jun 7, 2016 at 13:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .