Let a = 349, M = 492186.
Show that gcd(a;M) = 1.
Hence find the mutliplicative inverse,
a^-1 mod M
349 is a prime number. Its only integer factors are 1 and 349.
492,186 = 1*2*3*82031 (integer prime factors)
The only common factor is 1. That is the greatest common divisor.
I don't understand your inverse a^-1 method
By modular inverse, we look for
a-1 such that
a*a-1 ≡ 1 mod M
In other words, we look for x in
ax-qM=1
where x is the modular multiplicative inverse.
There are many ways to calculate a-1.
1. Trial and error
The easiest (but long) is by trial and error by calculating the product ax-qm=1 for values of q=1 to a-1.
In this case, the value of q=309, which makes a lot of calculations with the calculator.
2. extended Euclid's algorithm.
The GCF can be found by Euclid's algorithm. The extended algorithm continues (in reverse) the GCF calculation to find a-1.
Numerous implementations are available, some are better than others, depending on whether the method will be calculated by hand, or by computer, and in the latter case, by recursivity or not.
Here's a link to the description of the implementations.
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
One particular method of implementation for hand calculations is shown in this link:
http://marauder.millersville.edu/~bikenaga/numbertheory/exteuc/exteuc.html
and the corresponding calculations shown below. We create a table to calculate the GCF by Euclid's algorithm using the first two columns. The first column (a) stores the successive factors, and the second column the quotient (q).
When the first column reaches 1, that demonstrates that a and M are coprime.
We then fill column three (y) upwards, starting with a zero and 1 at the bottom. The next value of q is calculated by the product of q and y plus the previous (lower) y. The top value of y is the factor we look for.
Here's the table:
a q y
492186 - 56411
349 1410 40
96 3 11
61 1 7
35 1 4
26 1 3
9 2 1
8 1 1
1 8 0
Example entries:
First column: 96=492186-1410*349
Third column: 40=3*11+7
Finally, from the table, cross multiply the top entries of columns a and y to get:
492186*40-349*56411=1
which implies that
349*(492186-56411)≡1 mod(492186)
So the modular inverse is
492186-56411=435775.
BRO ITS 2 IDIOT
To show that gcd(a, M) = 1, we need to prove that a and M are coprime, or in other words, they have no common factors other than 1.
To find the gcd(a, M), we can apply the Euclidean Algorithm, which involves dividing the larger number by the smaller number repeatedly until we reach a remainder of 0.
Let's begin by comparing a and M:
a = 349, M = 492186
Step 1: Divide M by a and find the remainder.
492186 ÷ 349 = 1410 with a remainder of 216
Step 2: If the remainder is not 0, divide the previous divisor (a) by the remainder and find the new remainder.
349 ÷ 216 = 1 with a remainder of 133
Step 3: Repeat step 2 until the remainder is 0.
216 ÷ 133 = 1 with a remainder of 83
133 ÷ 83 = 1 with a remainder of 50
83 ÷ 50 = 1 with a remainder of 33
50 ÷ 33 = 1 with a remainder of 17
33 ÷ 17 = 1 with a remainder of 16
17 ÷ 16 = 1 with a remainder of 1
16 ÷ 1 = 16 with a remainder of 0
Since we have reached a remainder of 0, the gcd(a, M) is the last nonzero remainder we obtained, which is 1.
Therefore, we have proved that gcd(a, M) = 1, showing that a and M are coprime.
Next, to find the multiplicative inverse of a (denoted as a^(-1) mod M), we can use the Extended Euclidean Algorithm.
We will perform the Extended Euclidean Algorithm to find the coefficients x and y such that ax + My = gcd(a, M) = 1. The coefficient x will be the multiplicative inverse of a modulo M.
Using the above steps of the Euclidean Algorithm, we can rewrite each remainder in terms of the previous remainders until we reach the equation ax + My = gcd(a, M).
Starting from the last step:
1 = 17 - (1 × 16)
1 = 17 - (1 × (33 - 17))
1 = (-1 × 33) + 2 × 17
1 = (-1 × 33) + 2 × (50 - 33)
1 = 2 × 50 - 3 × 33
1 = 2 × 50 - 3 × (83 - 50)
1 = (-3 × 83) + 5 × 50
1 = (-3 × (133 - 83)) + 5 × 50
1 = 5 × 50 - 3 × 133
1 = 5 × (216 - 133) - 3 × 133
1 = 5 × 216 - 8 × 133
1 = 5 × 216 - 8 × (349 - 216)
1 = (-8 × 349) + 13 × 216
Comparing this equation to ax + My = gcd(a, M), we have found that x = -8 and y = 13. Since we are interested in the multiplicative inverse of a, we only need to consider x.
Therefore, the multiplicative inverse (a^(-1) mod M) is -8.
To obtain a positive value for the multiplicative inverse, we can add M to -8 until we get a positive value:
-8 + 492186 = 492178.
Hence, the multiplicative inverse of a mod M is 492178.