4 replies to this topic

[tim1234]

I've written a program in C to find the highest common factor of two integers, i need to add to it so that I can solve the ax + by = hcf(a,b) where x and y are integers. I've managed to program a trial and error method but that takes ages. Any ideas?

Cheers

[tim1234]

don't worry i worked it out :)

[Cosmet]

What was the solution?

[tim1234]

i needed to perform a series of recursive relationships which i did using arrays.

let a[0] = m, a[1] = n
q[k] = a[k-1]/a[k]
a[k+1] = a[k-1] - a[k]q[k]
if a[p+1]=0 then a[p] is hcf m,n

let x[0]=1, x[1]=0, y[0]=0 y[1]=1 and use the same recursion as above and you get a[p] = nx[p] + my[p]

[WingedPanther]

I posted some code for this in another post...Moving Elements in an Array.