Finding inverses in modular arithmetic

  • Thread starter PsychonautQQ
  • Start date
  • Tags
    Arithmetic
In summary, there are two methods for calculating the inverse of a number in a modular setting. The first is by applying the Bezout theorem and using the Euclidean algorithm to find the inverse. The second method is by using Euler's theorem and calculating the Euler totient function.
  • #1
PsychonautQQ
784
10
Hey PF!

Is there a systematic way to calculate the inverse of a number in a modular setting (modular setting? is that what I call it? lol).

How about 108x == 1 (mod 625), wolfram alpha calculated x = 272, how could I have arrived at this number besides guess and check?
 
Mathematics news on Phys.org
  • #2
There are two nice methods.

The first is by applying the Bezout theorem. This states that if ##a## and ##b## are integers, then there are integers ##p## and ##q## such that ##pa+bq = \text{gcd}(a,b)##. In this case we take ##a=108## and ##b=625##. The gcd is ##1## (which is a necessary and sufficient condition for finding inverses). So we search for integers ##p## and ##q## such that ##108p + 625q=1##. Our ##p## will be the inverse (just look at the equation (mod 625)).

How to find ##p## and ##q##? Well, we have the Euclidean algorithm for finding the gcd. So let's do that:

##625 = 108\cdot 5 + 85##
##108 = 85\cdot 1 + 23##
##85 = 23\cdot 3 + 16##
##23 = 16\cdot 1 + 7##
##16 = 7\cdot 2 + 2##
##7 = 2\cdot 3 + 1##
See http://en.wikipedia.org/wiki/Euclidean_algorithm for the details if this is unfamiliar. So we see indeed that the gcd is ##1##. Now let us do the Euclidean algorithm in reverse:

[tex]
\begin{eqnarray*}
1 & = & 7 - 2\cdot 3\\
& = & 7 - (16 - 7\cdot 2)\cdot 3\\
& = & 7\cdot (1 + 2\cdot 3) - 16\cdot 3\\
& = & 7\cdot 7 - 16\cdot 3\\
& = & (23 - 16\cdot 1)\cdot 7 - 16\cdot 3\\
& = & 23\cdot 7 - 16\cdot (1\cdot 7 + 3)\\
& = & 23\cdot 7 - 16\cdot 10\\
& = & 23\cdot 7 - (85 - 23\cdot 3)\cdot 10\\
& = & 23\cdot (7 + 3\cdot 10) - 85\cdot 10\\
& = & 23\cdot 37 - 85\cdot 10\\
& = & (108 - 85\cdot 1)\cdot 37 - 85\cdot 10\\
& = & 108\cdot 37 - 85\cdot (1\cdot 37 +10)\\
& = & 108\cdot 37 - 85\cdot 47\\
& = & 108\cdot 37 - (625 - 108\cdot 5)\cdot 47\\
& = & 108\cdot (37 + 5\cdot 47) - 625\cdot 47\\
& = & 108\cdot 272 - 625\cdot 47
\end{eqnarray*}[/tex]

Thus we get
[tex]1 = 108\cdot 272 - 625\cdot 47[/tex]
Looking at this equation in (mod 625), we get ##108\cdot 272 = 1##. So the inverse of 108 is 272.

A second method is by Euler's theorem (the generalization of Fermat's little theorem): This states that if ##\text{gcd}(a,n)=1##, then ##a^{\varphi(n)} = 1## in (mod n). In our case, we get ##108^{\varphi(625)} = 1## in (mod 625). So the inverse is ##108^{\varphi(625)-1}##. Now we need to calculate the Euler totient function ##varphi##. There are several methods, but let us use this one: http://en.wikipedia.org/wiki/Euler's_totient_function#Euler.27s_product_formula
So since ##625 = 5^4##, we get
[tex]\varphi(625) = 625\cdot (1 - \frac{1}{5}) = 625 - 125 = 500[/tex]
So the inverse is ##108^{499}##. This is an easier method to calculate the inverse, but it is more annoying since it leaves us with a tough exponential to calculate. A somewhat similar method but with smaller exponential can be found here http://en.wikipedia.org/wiki/Carmichael_function
 

1. What is modular arithmetic?

Modular arithmetic is a mathematical system that deals with integers and their remainders when divided by a fixed number, called the modulus. It is often used in cryptography and computer science.

2. Why do we need to find inverses in modular arithmetic?

Inverses in modular arithmetic are used to solve equations and perform operations that involve modular arithmetic. They also have applications in cryptography and error correction.

3. How do you find the inverse of a number in modular arithmetic?

To find the inverse of a number in modular arithmetic, you can use the extended Euclidean algorithm or the Fermat's little theorem. These methods involve finding the greatest common divisor between the number and the modulus.

4. Can every number have an inverse in modular arithmetic?

No, not every number has an inverse in modular arithmetic. A number must be relatively prime to the modulus in order to have an inverse. If a number and the modulus have a common factor, then the inverse does not exist.

5. How are inverses used in cryptography?

Inverses in modular arithmetic are used in cryptography to encrypt and decrypt messages. They are also used in key generation and authentication protocols. Inverses are essential in ensuring the security and effectiveness of many modern encryption algorithms.

Similar threads

Replies
5
Views
1K
Replies
1
Views
2K
  • General Math
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
997
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
2K
  • Beyond the Standard Models
2
Replies
41
Views
12K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Linear and Abstract Algebra
Replies
1
Views
1K
Back
Top