What is the smallest integer $n$, greater than $1$, such that $n^{-1}\pmod{1320}$ is defined?
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}\)