Using GCD to find unknown value

156 Views Asked by At

Given the equation:

$ k = a(b-f) - ag$

If :

  • a, b and f is unknown

  • k is known

  • ag is known

  • a(b-f) is known

Can we find what a is?

1

There are 1 best solutions below

0
On BEST ANSWER

Not necessarily directly. Because: $$\gcd(k,a(b-f))\geq a\tag{1}$$And,$$\gcd(k,ag)\geq a\tag{2}$$ And, $$\gcd(a(b-f),ag)\geq a\tag{3}$$

Gets us an upper bound on a, unless k has just 1 divisor less than this (1 is a divisor trivially sadly) we can't get an exact value yet. But, putting each possible a value through a similar test might help. Especially, if we can find $$\gcd((b-f),g)=1$$ forced that may help. Edit if g is known (as of posting this edit it wasn't listed as unknown.) GCD isn't needed $${ag\over g}= a$$