CODEWITHSUNDEEP
javaalgorithmmodulus
O.AEESS
O.AEESS

Reputation: 9

Using Euclidean algorithm in java

If I have x= 11 and y = 6 and I want to calculate (w*x)mod(y) = 1 . In other words how can I calculate the number that if multiplied by 11 and then modulus 6 the result 1. In this case w should be equal to 5. Is there anyway I can calculate the w in a method using Euclidean algorithm in java? Thank you!

Upvotes: 0

Views: 636

Answers (1)

blazs
blazs

Reputation: 4845

There is a theorem that says that the linear congruence a * x = b (mod n), where a, b, and n are integers, has a solution if and only if gcd(a, n) = 1.

Since gcd(11,6) = 1, which is simply because 11 is a prime number, your equation is indeed solvable.

To answer the question, no, you cannot solve the linear congruence using Euclid's algorithms---however, you can do that using extended Euclid's algorithm---, but you can use it so verify that the equation is solvable.

Once you find that gcd(a,n)=1, you compute the solution as x = b*r mod n, where r = a^-1 (mod n). To compute the inverse of a, which here we denoted r, you can use the extended Euclidean algorithm (abbreviated EEA).

If gcd(a,n)=1, then EEA, given a and n, computes r and s such that a*r + n*s = 1. We claim that r is the inverse of a modulo n. Once you have r, you compute x = b * r mod n.

These algorithms are nicely described in the book Introduction to Algorithm by Cormen et al.

Upvotes: 1

Related Questions