Login
Search
Welcome to the iTechForums.
If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.
To register now click here.
Latest Threads
Advertisements
Forum Statistics
Threads:
Posts: 2
Members:
Number of Users Online:
Welcome to our newest member,
Reply
 
Thread Tools Display Modes
  #1  
Old 05-13-2008, 08:18 AM
amoora amoora is offline
Junior Member
 
Join Date: May 2008
Posts: 1
Default

Using Euclid's Algorithm to find a solution in the integers?


I have 2 problems. One has been solved and the other I tried, following the example of the 1st, but I am missing a piece of the puzzle.

1) 4x + 6y = 18
Doing Euclid's Algorithm: 6/4 = 1R2; 4/2 = 2R0 thererfore, 2 is the GCD of 4 & 6 and divides 18, so a solution exists.
Now divide everything in original equation by 2 giving 2x + 3y = 9.
Now the part I don't get, but have written down, says to let y=9 then 2x=-18 and x= -9. How was it determined that y=9?


2) The next problem is 21x + 51y = 3
After doing Euclid's Algorithm, I found that 3 is the GCD, and divided the original equation by 3, giving 7x + 5y = 1
Where do I go from here?
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #2  
Old 05-13-2008, 08:18 AM
knashha knashha is offline
Junior Member
 
Join Date: May 2008
Posts: 1
Default

1) For the first equation , 2x+3y = 9 note that 3 must divide x
so write x= 3t. Then 6t+3y=9 and y=3-2t. The solution is
x=3t, y=3-2t for all integers t .

2) The second equation reduces to 7x+17y = 3 . To find
the solution reduce this mod 7 to get 0+3y = 3 mod 7 so
that y=1mod 7, and set y= 7t+1. Plug this in and solve for x,
7x+17(7t+1) = 3 and x = - 17t - 2. So all solutions in
integers are given by x= -17t -2 and y=7t+1 for all integer
values of t.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
BSD root: md0, major 2, minor 0 (SOLUTION)? Jazzy F *BSD 4 07-05-2008 08:21 PM
Let n be a large +ve integer.Is there any efficient algorithm which can find... kukur_diamond Software Design & Algorithms 0 05-08-2008 08:06 AM
How do you find a pattern or Algorithm in a bunch of numbers? ganjawars.ru Software Design & Algorithms 1 05-06-2008 10:39 PM
Let n be a large +ve integer.Is there any efficient algorithm which can find... kukur_diamond Software Design & Algorithms 0 05-06-2008 06:24 PM
I'm looking for an algorithm to find three numbers with sum equal to 0? george marti Software Design & Algorithms 0 05-06-2008 09:32 AM

Your Ad Here

All times are GMT. The time now is 03:10 PM.