+0  
 
0
1660
1
avatar

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

 May 21, 2019
 #1
avatar+26364 
+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}\)

 

 

laugh

 May 21, 2019
edited by heureka  May 22, 2019

1 Online Users

avatar