Algebra and Number Theory Question

eamoss

Hi im doing a repeat exam(from 1st sems) next month and im finding it hard looking back through my notes.

Ok question one(:D) from 2006
http://library.nuim.ie/expert2/downloads//2006-MT158-Main.pdf

My work
http://img231.imageshack.us/my.php?image=dsc01367co7.jpg
I've found the GCD which is 4 but I cant for the life of me remember how to the 2nd bit.

Step by step help would be greatly appreciated.

aequinoctium

4 divides 22972 so multiply x & y be this quotient.
there's one answer.

seandoiler

aequinoctium wrote:

4 divides 22972 so multiply x & y be this quotient.
there's one answer.

4 = 244.29 - 272.26

so x=-26, y=29 in part (i), as in quote, divide 22972 by gcd(244,272)=4 and multiply the x and y by this number, now this gives a particular solution to (ii) ie x_0=-149318 and y_0=166547, now to obtain a full solution, we simply extend this solution to x=-149318 + 61n, y=166547 - 68n

in general for an equation a*x + b*y = c, the solution set is given by
{ x_0 +( (n*b) / gcd(a,b) ) , y_0 - ( (n*a) / gcd(a,b)) }, where {x_0,y_0} is a known particular solution of the equation and n is an integer

eamoss

Sorry when i said the 2nd bit it was talking about the 2nd bit of 1(i) how to find x & y.

seandoiler

eamoss wrote:

Sorry when i said the 2nd bit it was talking about the 2nd bit of 1(i) how to find x & y.

but you have this answered already on the page you showed us....you can just work backwards from the calculation of the gcd
4 = 20 -8*2
= 20 - (28 -20)*2 ...using next line up
= ... etc
= 244*29 - 272*26

you just seem to work it out slightly slightly differently, you start with 28 = 272 -244 and you then let 272 = a and 244 = b, so 28 = 272 -244 = a - b,
now 20 = 244 - 28*8 = b - (a - b)*8 = 9*b - 8*a
now 8 = 28 - 20 = (a - b) -(9*b - 8*a) = 9*a - 10*b
now 4 = 20 - 8*2 = 9*b - 8*a - (9*a - 10*b)*2 = 29*b-26*a

LeixlipRed

eamoss, dunno if you're interested but I tutor for the Maths Dept in Maynooth and I'm giving grinds for the repeats. PM me if you need help