# Reverse substitution to find the inverse of modular arithmetic

• chwala
In summary: The answer is yes, it does. If we subtract two remainders, the result is always the leftover minus the first remainder. This is called the distributive property.The distributive property is a very important principle in mathematics. It says that for any set of operations (plus, minus, multiply, etc.), there is a unique set of rules that governs how the operations combine.
chwala
Gold Member
Homework Statement
how do we find the inverse of 1973 given gcd (132,289,1973)
Relevant Equations
modular arithmetic and co prime...
##132,289≡1973* 67 + 98##
##1973≡98*20+13##
##98≡13*7+7##
##13≡7*1+6##
##7≡6*1+1##
now in reverse my attempt is as follows,
##1≡7-6##
## 1≡7-(13-7)##
##1≡2*7-(1973-20*132,289+1340*1973)##
##1≡2*7-(1341*1973-20*132,289##
which is correct but my interest is in finding the inverse of 1973 help?

i do not get you...

chwala said:
i do not get you...

Are you familiar with Bezout's theorem?
It says that if gcd(a,b)=1, then you can find integers s,r such that sa + rb=1.

Now, if you want to find an inverse of say a modulo b, you can take mod b of both sides to obtain sa = 1 mod b and then you have found that s is the inverse of a mod b.

Here you can do the same thing, but you have to express 1 as a 'good' linear combination of the two numbers you take the gcd from, and in your attempt it isn't written in the right way.

chwala
Math_QED said:
Are you familiar with Bezout's theorem?
It says that if gcd(a,b)=1, then you can find integers s,r such that sa + rb=1.

Now, if you want to find an inverse of say a modulo b, you can take mod b of both sides to obtain sa = 1 mod b and then you have found that s is the inverse of a mod b.

Here you can do the same thing, but you have to express 1 as a 'good' linear combination of the two numbers you take the gcd from, and in your attempt it isn't written in the right way.
can you show me how to write 1 in good form...

chwala said:
Problem Statement: how do we find the inverse of 1973 given gcd (132,289,1973)
Relevant Equations: modular arithmetic and co prime...

##132,289≡1973* 67 + 98##
##1973≡98*20+13##
##98≡13*7+7##
##13≡7*1+6##
##7≡6*1+1##
now in reverse my attempt is as follows,
##1≡7-6##
## 1≡7-(13-7)##
##1≡2*7-(1973-20*132,289+1340*1973)##
##1≡2*7-(1341*1973-20*132,289##
which is correct but my interest is in finding the inverse of 1973 help?
The inverse of ##1973## is ##\frac{1}{1973}##. I think you meant inverse modulo some ##n##, which one? To do modular arithmetic, you will have to know the module first!

You can write your equation as ##1= 1973\cdot m + r \Longleftrightarrow m\cdot 1973 =1-r##. Then apply the module. E.g. if ##n=1973## then ##0 \equiv m\cdot 1973 \equiv 1-r \mod \,1973 \Longrightarrow 1\equiv r \mod \,1973##. If ##n=r## then ##m\cdot 1973 \equiv 1-r \equiv 1 \mod \,1973 ##.

ok i am getting
##1≡-149*1973+2*132289+15*98*20##
i am interested in the inverse this implies that the multiplicative inverse is ##-149##

i am sorry, i wrote the problem incorrectly. Most importantly, i now understand the Extended Euclidean algorithm..now i get it. The problem statement should have read:

problem statement
how do we find the multiplicative inverse for ##1973## given gcd##(65762,1973)## ?

my working is as follows;

##65762=1973*33+653##
##1973≡653*3+14##
##653≡14*46+9##
##14≡9*1+5##
##9≡5*1+4##
##5≡4*1+1##

actually my problem was to find the multiplicative inverse and the following is my attempt;

##1≡5-1*4##
##1≡(14-9)-1*4##
##1≡(1973-3*653)-(14-9)##
##1≡2(14-9)-(653-46*1973+138*653)##
##1≡2[(1973-3*653)-(653-14*46)]-[(653-46*1973+138*653)]##...
##1≡(2)1973+(264)1973+(92)1973+(9108)1973+(4587)1973+(46)1973+(-8)65762+(-276)65762+(-139)65762##
##1≡(14099)1973+(-423)65762##
implying that the multiplicative inverse for ##1973## is ##14099##

bingo from Africa, bingo!

Last edited:
fresh_42 said:
The inverse of ##1973## is ##\frac{1}{1973}##. I think you meant inverse modulo some ##n##, which one? To do modular arithmetic, you will have to know the module first!

You can write your equation as ##1= 1973\cdot m + r \Longleftrightarrow m\cdot 1973 =1-r##. Then apply the module. E.g. if ##n=1973## then ##0 \equiv m\cdot 1973 \equiv 1-r \mod \,1973 \Longrightarrow 1\equiv r \mod \,1973##. If ##n=r## then ##m\cdot 1973 \equiv 1-r \equiv 1 \mod \,1973 ##.

you're right, i meant the multiplicative inverse as indicated above...

I noticed a trend in your number theory problems. You have a lack of understanding of Number Theory fundamentals. I think better time would be spent actually going through a number theory textbook.

A thorough book would be Elementary Number Theory by Charles Vanden Eynden. An easier book, but thorough in its explanations would be by Pommersheim. The Pommersheim book is more pricey, but it may be better for you're case.

chwala
Do you even understand why a multiplicative inverse exist?

chwala
I need to read more on this area,... Of course I know the the meaning of multiplicative inverse in respect to two primes and the encryption and decryption ...I will all the same take your advice.

Last edited:
MidgetDwarf said:
Do you even understand why a multiplicative inverse exist?

I am learning... I don't know everything. Actually find attached the problem that I was attempting to solve using the.. modular multiplicative inverse.

#### Attachments

• Screenshot_20190618-220127.png
51.7 KB · Views: 265
chwala said:
I am learning... I don't know everything. Actually find attached the problem that I was attempting to solve using the.. modular multiplicative inverse.
The basic idea is, that we can calculate with the remainders of a certain division. E.g. a division by ##5## has the possible remainders ##0,1,2,3,4##. All of them can be added and multiplied, such that we get again a remainder of division by ##5##. Say ##2 \cdot 3 = 6## which has the remainder ##1##. Thus ##2\cdot 3 \equiv 1 \mod 5##. And if you check then you will see that all integers with remainder ##2## multiplied by any integer with remainder ##3## always results in an integer with remainder ##1##. The same is true for addition.

This immediately raises the question, whether subtraction and division is also possible. Subtraction is no problem. Multiplication is a bit more complicated. In case of the module ##5## as above, all elements ##1,2,3,4## (of course not ##0##) can be inverted, hence we can divide with them. E.g. we have already seen that ##2\cdot 3 = 1##, which means ##2^{-1}= 3## and ##3^{-1}=2##. The reason that it works is, because ##5## is a prime and all integers other than zero are coprime to ##5##.

If we had for example division by ##6##, a module ##6## or ##6\mathbb{Z}## to be precise, we get ##2\cdot 3 =6 \equiv 0 \mod 6## and we cannot divide neither with ##2## nor with ##3##. They do not have inverses. Coprime remainders as ##1## and ##5## have inverses, ##2,3,4## do not.

You see, the situation changes if we change the module. The Euclidean algorithm you performed above can be used to find an inverse, the way you did it.

chwala
Yeah. that's the key idea in RSA. It requires Euler Totient Function. The book by Pommersheim has an explanation of different types of encryption and why RSA is better than the previous encryption shown in the text. Yes, multiplicative inverse is important. I suggest buying the book, before trying to solve anything more. It would make way better use of your time, and you gain more. Then, if you have studied a bit more of analysis, you can move onto Apostol: Analytical Number Theory.

chwala
Thanks, i think with the attachment on the rsa problem, you can now understand why i was looking for the multiplicative inverse...my area of speciality was in applied maths, i will nevertheless take Midget's advice to do more reading on number theory. regards,

Last edited:
MidgetDwarf said:
I noticed a trend in your number theory problems. You have a lack of understanding of Number Theory fundamentals. I think better time would be spent actually going through a number theory textbook.

A thorough book would be Elementary Number Theory by Charles Vanden Eynden. An easier book, but thorough in its explanations would be by Pommersheim. The Pommersheim book is more pricey, but it may be better for you're case.

Modular arithmetic is quite a narrow ranged field, and if your emphasis is on its applications, you probably won't need the entire theory of commutative rings or Galois theory. I have searched a few links on Google and found a lot of, well, trash. But these are good reads:

https://pdfs.semanticscholar.org/331c/f92e3155b765aede69ef8e6dedc3319f5eb6.pdfhttp://www2.math.uu.se/~astrombe/talteori2016/lindahl2002.pdfhttp://homepages.warwick.ac.uk/staff/J.E.Cremona/courses/MA257/ma257.pdf
All of them contain the Chinese Remainder Theorem (which is a must) and the first two contain also RSA, but therefore the third mentions Bezout's Lemma.

chwala
chwala said:
The Van Eyden Book is fairly cheap if you get an older edition. However, it is not easier to read.

chwala
asking for pdf of books on physicsforumns is against the site rules due to copyright infringement, unless the book is an open source or has been made available for free to the public by the publisher.

Not sure how expensive books are where you are from.But you would get a lot from the Pommersheim or a similar book. Since you said training was in applied math. Then I assume you have a degree. So maybe the cost of the book can be thought can be justified by not going out to dinner or hanging out with friends for a while.

Last edited by a moderator:
chwala
fresh_42 said:
Modular arithmetic is quite a narrow ranged field, and if your emphasis is on its applications, you probably won't need the entire theory of commutative rings or Galois theory. I have searched a few links on Google and found a lot of, well, trash. But these are good reads:

https://pdfs.semanticscholar.org/331c/f92e3155b765aede69ef8e6dedc3319f5eb6.pdfhttp://www2.math.uu.se/~astrombe/talteori2016/lindahl2002.pdfhttp://homepages.warwick.ac.uk/staff/J.E.Cremona/courses/MA257/ma257.pdf
All of them contain the Chinese Remainder Theorem (which is a must) and the first two contain also RSA, but therefore the third mentions Bezout's Lemma.
Thanks Fresh,..greetings to you brother.

## What is reverse substitution in modular arithmetic?

Reverse substitution is a method used to find the inverse of a number in modular arithmetic. It involves finding a number that, when multiplied by the original number, gives a remainder of 1 when divided by the modulus.

## Why is reverse substitution used in modular arithmetic?

Reverse substitution is used to find the inverse of a number in modular arithmetic because it allows us to solve equations and perform operations that would otherwise be impossible. It is especially useful in cryptography and coding theory.

## How do you perform reverse substitution to find the inverse of a number in modular arithmetic?

To perform reverse substitution, you need to follow these steps:

1. Write the equation in the form of a congruence, with the original number on one side and the modulus on the other side.
2. Use the extended Euclidean algorithm to find the greatest common divisor (GCD) of the original number and the modulus.
3. Write the GCD as a linear combination of the original number and the modulus.
4. Take the coefficient of the original number and use it as the inverse in the congruence equation.

## Can reverse substitution be used for any modulus?

Yes, reverse substitution can be used for any modulus as long as the modulus and the original number are relatively prime. If they are not relatively prime, the inverse will not exist.

## Are there any limitations to using reverse substitution in modular arithmetic?

One limitation of reverse substitution is that it can only find the inverse of a number in modular arithmetic. It cannot be used to find the inverse of a number in regular arithmetic. Additionally, it can only find the inverse for relatively prime numbers, as mentioned earlier.

• Calculus and Beyond Homework Help
Replies
3
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
9
Views
1K
• Calculus and Beyond Homework Help
Replies
32
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
9
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
412