+0

0
511
1

What is the smallest integer $n$, greater than $1$, such that $n^{-1}\pmod{1320}$ is defined?

May 21, 2019

#1
+25228
+3

What is the smallest integer n, greater than 1, such that $$n^{-1}\pmod{1320}$$is defined?

According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
$${\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}$$
where  $${\displaystyle \phi }$$   is Euler's totient function.
A modular multiplicative inverse can be found directly:
$${\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}$$
n must be coprime to 1320 or gcd(n,1320) = 1,

Factorization of 1320:

$$1320 = 2^3×3×5×11$$ (6 prime factors, 4 distinct)

The smallest integer n > 1 coprime to 1320 is 7.

$$\begin{array}{|rcll|} \hline && 7^{-1}{\pmod {1320}} \\ &\equiv& 7^{\phi (1320)-1}{\pmod {1320}} \quad | \quad \phi (1320) = 320 \\ &\equiv& 7^{320-1}{\pmod {1320}} \\ &\equiv& 7^{319}{\pmod {1320}} \\ &\equiv& \mathbf{943} {\pmod {1320}} \\ \hline \end{array}$$

May 21, 2019
edited by heureka  May 22, 2019