# Thread: HCF and Dividing Numbers

1. ## HCF and Dividing Numbers

Prove that xa+yb=c has integer solution x, y iff hcf(a,b)|c.
I have to prove this both ways, because of the iff statement. So first, I let d = hcf(a,b) and assume it divides c, to show that xa+yb=c has integer solutions.

1) xy + yb = c
2) (xa)/d + (yb)/d = c/d
3) x(a/d) + y(b/d) = c/d
4) By the definition of the HCF, d|a, d|b, so a/d, b/d are integers. If c/d (by assumption) is an integer too, there will be integers x, y that satisfy the above equasion.

Now, I have to assume that xa+yb=c has integer solutions, and then show that d|c to finish the proof, but I dont know where to start, does anyone have any suggestions?

1) ???

Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
I've attempted the above problem, and been advised to prove that both sides of the equasion divide the other, and hence, they're both equal. However, I've hit at some contradictions, and I'd like to know where I'm going wrong.

1) Let c = hcf(na,nb), and d = n*hcf(a,b). Note that n|d.
2) Note that c|na, c|nb and thus, c|n.
3) c|n and n|d => c|d.
4) Now, consider c/d = c/n * c/hcf(a,b).

Now, I want to show that both of those are integers, thus making c/d an integer, thus showing that d|c and proving the statement. But, I can't seem to show how. Can anyone help me with my proof?

2. Originally Posted by bumcheekcity
I have to prove this both ways, because of the iff statement. So first, I let d = hcf(a,b) and assume it divides c, to show that xa+yb=c has integer solutions.

1) xy + yb = c
2) (xa)/d + (yb)/d = c/d
3) x(a/d) + y(b/d) = c/d
4) By the definition of the HCF, d|a, d|b, so a/d, b/d are integers. If c/d (by assumption) is an integer too, there will be integers x, y that satisfy the above equasion.

Now, I have to assume that xa+yb=c has integer solutions, and then show that d|c to finish the proof, but I dont know where to start, does anyone have any suggestions?

1) ???

I've attempted the above problem, and been advised to prove that both sides of the equasion divide the other, and hence, they're both equal. However, I've hit at some contradictions, and I'd like to know where I'm going wrong.

1) Let c = hcf(na,nb), and d = n*hcf(a,b). Note that n|d.
2) Note that c|na, c|nb and thus, c|n.
3) c|n and n|d => c|d.
4) Now, consider c/d = c/n * c/hcf(a,b).

Now, I want to show that both of those are integers, thus making c/d an integer, thus showing that d|c and proving the statement. But, I can't seem to show how. Can anyone help me with my proof?
I assume hcf = highest common factor (I learned it as greatest common divisor).

This isn't a proof, just the method I would use to approach it.

Consider n divides na, and na can be broken down into a prime factorization.
And n divides nb, and nb can be broken down into a prime factorization.

And the highest common factor of two numbers in their prime factorization form is the lowest value of the exponent of each prime factor

So, for example, if a = 20, then it's prime factorization is $\displaystyle 2^{2}\cdot 5$ and if b = 25 then it's prime factorization is $\displaystyle 5^{2}$ and so the highest common factor is
$\displaystyle 2^{min(2,0)}\cdot 5^{min(1,2)} = 2^{0}\cdot 5^{1} = 5$

Now, if you multiply both numbers by an integer n, then the prime factorization of n will be in both numbers prime factorization, and will consequently be in the answer for the hcf(na, nb) which means that n divides hcf(na, nb). and n * hcf(a,b) = hcf(na,nb)

So like lets say our last problem we chose n=15, then na=15*20=300, and the prime factorization of na is
$\displaystyle 2^{2}\cdot 3\cdot 5^{2}$ and nb = 15*25=375 then it's prime factorization is $\displaystyle 3\cdot 5^{3}$ and so the highest common factor is
$\displaystyle 2^{min(2,0)}\cdot 3^{min(1,1)}{\cdot 5^{min(2,3)} = 2^{0}\cdot 3^{1} 5^{2} = 75$

and 15 divides 75, leaving 5 leftover. $\displaystyle \frac{hcf(na,nb)}{n} = hcf(a,b)$

I hope that made sense, I'm really bad at writing proofs, so I just wanted to give you an example of what method I think would be easiest to show it.

3. Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
----------------------------------------------

let d=hcf(na,nb). then $\displaystyle 1 = hcf \left( {\frac{na}{d},\frac{nb}{d}}\right) = hcf \left( {\frac{n}{d}a,\frac{n}{d}b}\right)$

$\displaystyle \implies \frac{d}{n} = hcf(a,b)$
$\displaystyle \implies$ hcf(na,nb) = n*hcf(a,b)

4. Let $\displaystyle a,b\in \mathbb{Z}^+$ and suppose that $\displaystyle ax+by=c$ has a solution in $\displaystyle x,y\in \mathbb{Z}$ for $\displaystyle c\in \mathbb{Z}^+$. Then $\displaystyle \gcd(a,b) = d$ divides the LHS and so it must divide the RHS i.e. $\displaystyle d|c$. Now we need to prove the converse, since $\displaystyle d=\gcd(a,b)$ we can write $\displaystyle ax'+by' = d$ for $\displaystyle x',y'\in \mathbb{Z}$ since $\displaystyle d|c\implies c=dk$ so $\displaystyle a(x'k)+b(y'k) = dk = c$ and so $\displaystyle x'k,y'k$ are solutions. Q.E.D.

5. Originally Posted by kalagota
Prove that hcf(na,nb) = n*hcf(a,b) for a, b, n integers, and n > 0
----------------------------------------------

let d=hcf(na,nb). then $\displaystyle 1 = hcf \left( {\frac{na}{d},\frac{nb}{d}}\right) = hcf \left( {\frac{n}{d}a,\frac{n}{d}b}\right)$

$\displaystyle \implies \frac{d}{n} = hcf(a,b)$
$\displaystyle \implies$ hcf(na,nb) = n*hcf(a,b)
Thankyou all very much for your help. But I have a quick question. The logical step inbetween line 1 and line 2 of this proof means you take a 'factor' of n/d out of the HCF. But this is what we are trying to prove, surely? We are trying to prove that hcf(na,nb) = n*hcf(a,b), and taking the factor of n out of the HCF is assuming the solution to prove the solution, or am I missing a step?

6. indeed, there was a missing step (i thought it can easily be seen or i has been proven already)

okay, here it is.. (if hcf is just equivalent to gcd..)
if $\displaystyle d=gcd(na,nb)$, then d = rna + snb for some r,s integers which implies that $\displaystyle 1 = \frac{rna}{d} + \frac{snb}{d}$
$\displaystyle \implies 1 = \frac{n}{d}ra + \frac{n}{d}sb$
$\displaystyle \implies \frac{d}{n} = ra + sb$
whether $\displaystyle \frac {d}{n}$ an integer or not, it can be assume that $\displaystyle \frac{d}{n} = gcd(a,b) \implies d=n*gcd(a,b)$