Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: discrete structures
Replies: 9   Last Post: Apr 13, 2008 10:14 PM

 Messages: [ Previous | Next ]
 Nat Silver Posts: 2,082 Registered: 12/6/04
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.

Date Subject Author
2/24/08 Nichole
2/24/08 Mariano
2/24/08 magidin@math.berkeley.edu
2/24/08 quasi
2/24/08 magidin@math.berkeley.edu
2/24/08 quasi
2/24/08 Nichole
2/24/08 Nat Silver
2/25/08 Nichole
4/13/08 Bart Goddard