+0

# modular arithmetic

0
39
1

What is the smallest integer n, greater than 1, such that 1/n (mod 130)  and 1/n (mod 9) are both defined?

Jul 3, 2021

#1
+26115
+2

What is the smallest integer n, greater than 1, such that
$$\dfrac{1}{n} \pmod{130}$$ and $$\dfrac{1}{n} \pmod {9}$$

are both defined?

There is an invertible modulo 130, if $$\gcd(130,n)=1~$$(130 and n are relatively prime)
There is an invertible modulo 9, if $$\gcd(9,n)=1~$$ (9 and n are relatively prime)

$$n > 1$$

$$\begin{array}{|c|c|c|c|} \hline n & \gcd(130,n) & \gcd(9,n) \\ \hline 2 & \gcd(130,2)=2 & \gcd(9,2)=\color{red}1 \\ 3 & \gcd(130,3)=\color{red}1 & \gcd(9,3)=3 \\ 4 & \gcd(130,4)=2 & \gcd(9,4)=\color{red}1 \\ 5 & \gcd(130,5)=5 & \gcd(9,5)=\color{red}1 \\ 6 & \gcd(130,6)=2 & \gcd(9,6)=3 \\ \mathbf{7} & \gcd(130,7)=\color{red}1 & \gcd(9,7)=\color{red}1 & \checkmark \\ \hline \end{array}$$

The smallest integer is 7

$$\dfrac{1}{7} \pmod{130} \equiv 93 \text{ and } \dfrac{1}{7} \pmod {9} \equiv 4$$

Jul 4, 2021