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

Guest May 21, 2019

#1**+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}\)

heureka May 21, 2019