Reverse substitution to find the inverse of modular arithmetic

[chwala]

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?

 

[chwala]

i do not get you...

 

[member 587159]

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]

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...

 

[fresh_42]

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$.

So what is your module?

 

[chwala]

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$

 

[chwala]

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!

 

[chwala]

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$.

So what is your module?

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

 

[MidgetDwarf]

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.

 

[MidgetDwarf]

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.

 

[chwala]

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.

 

[fresh_42]

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.

 

[MidgetDwarf]

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,

 

[chwala]

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.

can you suggest a free download pdf book that i can download? The mentioned resources require some money...

 

[fresh_42]

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.

 

[MidgetDwarf]

can you suggest a free download pdf book that i can download? The mentioned resources require some money...

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

 

[MidgetDwarf]

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.

 

[chwala]

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.