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
Let a = 349, M = 492186.
Show that gcd(a;M) = 1.
Hence find the mutliplicative inverse,
a^-1 mod M
3 answers
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.
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
1 answer