Let a = 349, M = 492186.

Show that gcd(a;M) = 1.
Hence find the mutliplicative inverse,
a^-1 mod M

3 answers

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
Similar Questions
    1. answers icon 1 answer
  1. Task 2 (4pts)2a: Write inequality, show work and graph (2pts) 2b: Find Total Earnings, show all work. (1pt) 2c: Find Total
    1. answers icon 1 answer
    1. answers icon 1 answer
  2. what does this meanTask 2 (4pts) 2a: Write inequality, show work and graph (2pts) 2b: Find Total Earnings, show all work. (1pt)
    1. answers icon 1 answer
more similar questions