1. Let $m$ be a positive integer, and suppose that $9$ is its own inverse $\pmod m$, but $3$ is $\textbf{not}$ its own inverse $\pmod m$. How many possible values for $m$ are there?

2. There are finitely many primes $p$ for which the congruence $$8x\equiv 1\pmod{p}$$has no solutions $x$. Determine the sum of all such $p$.

Rollingblade May 17, 2018

#1

#2**+1 **

Hallo Melody.

In mathematics, in particular the area of number theory, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as

\( {\displaystyle ax\equiv 1{\pmod {m}}}\)

\(\text{We have $a = 9$ and $x =$ the inverse of integer $a$ } \\ {\displaystyle 9x\equiv 1{\pmod {m}}} \)

So "9 is its own inverse" means that \(\text{ $x=a=9 $}\)

Finally

\(\begin{array}{|rcll|} \hline 9\cdot 9 &\equiv& 1 \pmod m \\ \hline \end{array}\)

Source: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

heureka
May 17, 2018

#3**+2 **

Thanks Heureka,

I understand about half of that, at least I now know what 9 being its own inverse means.

So

9*9=1 (mod m)

81=1 (mod m)

so

80=0 (mod m)

Factors of 80 are 1, 2,4,5,8,10,16,20,40,80

This won't makes sense for 1,2,4,5, or 8

9*9 =81 = 1 (mod 10)

9*9 =81 = 1 (mod 16)

9*9 =81 = 1 (mod 20)

9*9 =81 = 1 (mod 40)

9*9 =81 = 1 (mod 80)

now 3*3=9 so this will stay 9 for any of the above mods.

So the possible values of m are 10,16,20,40, and 80 **There are 5 of them**

**Is this right Heureka or am I not understanding something?**

Melody
May 17, 2018

#4**+1 **

Hallo Melody,

this is right, but i think \(m =5 \) is a value for \(m\) too.

Here my table:

\(\begin{array}{|r|r|r|r|r|} \hline m & & & =1 & \ne 1 \\ \hline 1 & 9*9=81\equiv 0 \pmod 1 & 3*3=9\equiv 0 \pmod 1 & & \checkmark \\ 2 & 9*9=81\equiv 1 \pmod 2 & 3*3=9\equiv 1 \pmod 2 & \checkmark & \\ 4 & 9*9=81\equiv 1 \pmod 4 & 3*3=9\equiv 1 \pmod 4 & \checkmark & \\ \color{red}5 & 9*9=81\equiv 1 \pmod 5 & 3*3=9\equiv 4 \pmod 5 & \checkmark & \checkmark \\ 8 & 9*9=81\equiv 1 \pmod 8 & 3*3=9\equiv 1 \pmod 8 & \checkmark & \\ \color{red}10 & 9*9=81\equiv 1 \pmod{ 10} & 3*3=9\equiv 9 \pmod{ 10} & \checkmark & \checkmark \\ \color{red}16 & 9*9=81\equiv 1 \pmod{ 16} & 3*3=9\equiv 9 \pmod{ 16} & \checkmark & \checkmark \\ \color{red}20 & 9*9=81\equiv 1 \pmod{ 20} & 3*3=9\equiv 9 \pmod{ 20} & \checkmark & \checkmark \\ \color{red}40 & 9*9=81\equiv 1 \pmod{ 40} & 3*3=9\equiv 9 \pmod{ 40} & \checkmark & \checkmark \\ \color{red}80 & 9*9=81\equiv 1 \pmod{ 80} & 3*3=9\equiv 9 \pmod{ 80} & \checkmark & \checkmark \\ \hline \end{array}\)

So the possible values of **m** are ** 5,10,16,20,40, **and **80 ** There are **6** of them

heureka
May 17, 2018