Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Nat Silver

Posts: 2,082
Registered: 12/6/04
Re: discrete structures
Posted: Feb 24, 2008 9:32 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.