
Re: discrete structures
Posted:
Feb 24, 2008 9:32 PM


Nichole wrote:
> (a) Let n and a be positive integers with gcd(a, n)=1. > Prove that the equation a x?1(mod n) has a solution. > (b) Solve 271 x ? 1 (mod 1003) > (c) Solve 7008x ? 1(mod 7919) > > any ideas or thoughts??
Here's how to solve part b. Use the euclidean algorithm to find gcd(271, 1003) as follows: Divide 271 into 1003 to get: 1003  3(271) = 190. Divide 190 into 271 to get: 271  190 = 81 Divide 81 inot 190 to get: 190  2(81) = 28 Divide 28 into 81 to get: 81  2(28) = 25 Divide 25 into 28 to get: 28  25 = 3 Divide 3 into 25 to get: 25  8(3) = 1
Then gcd(271, 1003) = 1
Now we go back up the list we have made, substituting as we go, as follows:
25  8(3) = 1
25  8(2825) = 1, which gives 9(25)  8(28) = 1
9(812(28))  8(28) = 1, which gives 9(81)  26(28) = 1
9(81)  26(190  2(81)) = 1, which gives 61(81)  26(190) = 1
61(271  190)  26(190) = 1, which gives 61(271)  87(190) = 1
61(271)  87(1003  3(271)) = 1, which gives 322(271)  87(1003) = 1
Then 322(271) = 1 + 87(1003), and one solution of 271 x ? 1 (mod 1003) is x = 322.

