|
|
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(28-25) = 1, which gives
9(25) - 8(28) = 1
9(81-2(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.
|
|
