We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
56
1
avatar

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

 May 21, 2019
 #1
avatar+22358 
+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

21 Online Users

avatar