heureka

avatar
Usernameheureka
Score18539
Stats
Questions 11
Answers 3205

 #4
avatar+18539 
+4
heureka Sep 15, 2017
 #2
avatar+18539 
0

((51)^-1)mod26=?

or 51 inverse mod 26=?

 

\(\begin{array}{l} \text{In number theory, }\\ \text{Euler's theorem (also known as Euler's totient theorem)}\\ \text{states that if } \mathbf{m} \text{ and } \mathbf{a} \text{ are coprime positive integers, then }\\ \hline a^{\varphi (m)} \equiv 1 \pmod{m} \qquad \text{, if }~ gcd(a,m)=1 \\\\ \text{or} \\ \\ a^{\varphi (m)} \pmod{m} \equiv 1 \qquad | \qquad \cdot \frac{1}{a}\\ \frac{ a^{\varphi (m)} } {a} \pmod{m} \equiv \frac{1}{a} = a^{-1}\\ a^{\varphi (m)-1} \pmod{m} \equiv \frac{1}{a} = a^{-1}\\ \begin{array}{|rcl|} \hline a^{-1} = \frac{1}{a} \equiv a^{\varphi (m)-1} \pmod{m} \qquad \text{, if }~ gcd(a,m)=1\\ \hline \end{array} \end{array}\)

 

 We need this Formula:

\( \begin{array}{|lrcll|} \hline \text{Let } \varphi(n) \text{ denote the totient function. } \\ \hline \end{array} \)

 

 

Now we can calculate \(\frac{1}{51} \pmod {26} = \ ?\)

1. The greatest common divisor (gcd)

\(gcd(51,26) = 1\)

 

2. \(\varphi(26) = \ ?\)

\(\begin{array}{rcll} \varphi(26) &=& 26\cdot (1- \frac{1}{2} )\cdot (1- \frac{1}{13} ) \qquad \text{ because } ~ 26 = 2\cdot 13 \\ &=& 26\cdot \frac{1}{2} \cdot \frac{12}{13} \\ &=& 12 \\ \end{array}\)

 

3.

\(\begin{array}{rcll} \frac{1}{51} & \equiv & 51^{\varphi (26)-1} \pmod{26} \quad & | \quad \varphi(26)=12 \\ & \equiv & 51^{12-1} \pmod{26} \\ & \equiv & 51^{11} \pmod{26} \quad & | \quad 51\equiv -1 \pmod{26} \\ & \equiv & (-1)^{11} \pmod{26} \quad & | \quad (-1)^{11} = -1 \\ & \equiv & -1 \pmod{26} \\ & \equiv & -1+26 \pmod{26} \\ & \equiv & 25 \pmod{26} \\ \end{array} \)

 

Result:

\(\mathbf{\frac{1}{51} \pmod {26} = 25}\)

 

Proof:

\(\begin{array}{|rcll|} \hline && 51\cdot \frac{1}{51} \pmod{26} \\ &\equiv& 51\cdot 25 \pmod{26} \\ &\equiv& 1275 \pmod{26} \\ &\equiv& 1 \pmod{26} \ \checkmark\\ \hline \end{array} \)

 

laugh

heureka Sep 12, 2017