# Thread: GCD Problem

1. ## GCD Problem

I've been working on these two problems for the last few days, can't seem to get it. Any help would be very much appreciated.

1. Prove that a|bc iff a/(a,b)|c
So far I know that the denominator has to be a common multiple of both a & b, but I cannot prove that it has to be the gcd of a & b.

2. Show that if (a,b)=1, then (a+b,a2-ab+b2)=1 or 3
So far this is what I've come up with, using the theorems:
a) (a,m)=1, (b,m)=1, then (ab,m)=1
b) (a,b)=(a,b+na) that:

(a(a+b),b) = (a2+ab,b) = 1
(a,b(b-2a)) = (a,b2-2ab)=1

but I can't seem to relate the two.

Again, thanks for any help in advance.

2. 1. $a|bc \implies a|b \text{ or } a|c$
In the first case, $a|b \implies (a,b)=a \implies \frac{a}{(a,b)}=1|c$
In the second case, $a|c \implies (a,b) \text{ is at most } a \implies \frac{a}{(a,b)}|c$ because $\frac{a}{(a,b)}$ is a factor of a.
2. You have (2,3) = 1 but 2+3=1
Also (17,19) = 1 $(19-17)^2 = 4$
The statement I not true as I understand it.

3. (1) Since it's an if and only if statement, we have to show the statement forward and its converse is true.

(a) $a \mid bc \ \Rightarrow \ \tfrac{a}{(a,b)} \mid c$

Let $d = (a,b)$. For some $x,y \in \mathbb{Z}$, we have: $ax + by = d \ \Leftrightarrow \ \tfrac{a}{d}x + \tfrac{b}{d}y = 1 \ \Leftrightarrow \ \tfrac{a}{d}cx + \tfrac{b}{d}cy = c$

Since $\tfrac{a}{d}$ divides both terms on the left hand side (justify it), we can conclude $\tfrac{a}{d} \mid c$.

(b) $\tfrac{a}{(a,b)} \mid c \ \Rightarrow \ a \mid bc$

So we have: $\tfrac{a}{(a,b)} \mid c \ \Rightarrow \ a \mid (a,b)c$

Since $(a,b) \mid b$ by definition, then $(a,b)c \mid bc$.

Put those 2 lines together and we have our conclusion.
_______________________________

You have (2,3) = 1 but 2+3=1
Also (17,19) = 1 (19-17)^2 = 4
The statement I not true as I understand it.
The statement says that for all $a, b \in \mathbb{Z}$ such that $\gcd (a,b) = 1$, then $\gcd \left(a + b, a^2 - ab + b^2\right) = 1 \text{ or } 3$

For example, $a = 2$ and $b = 3$. Then: $\gcd(2 + 3, \ 2^2 - (2)(3) + 3^2) = \gcd(5, 7) = 1$

And another: $a = 10$ and $b = 11$. Then: $\gcd(10+11, 10^2 - (10)(11) + 11^2) = \gcd(21, 111) = 3$

4. I'm not totally sure but using euclidian algorythm we have
$a^2-ab+b^2=(a-2b)(a+b)+3b^2$
Now we have to search for common factors of $a+b \text{ and } 3b^2$
It is not b since $(a,b)=1$. It can thus be 1 or 3.

5. Thanks for your help with #1 o_O! (I can't believe I didn't see the obvious proof there... )

vincisonfire, I just learned the Euclidean algorithm yesterday, so I'm still trying to understand your reply. Thanks for your help though!

6. Originally Posted by vincisonfire
1. $a|bc \implies a|b \text{ or } a|c$
Thats not true in general!

Choose a = 4, b = 2 , c = 2, to understand why...