# Math Help - elem. # theo - gcd(a, a+n) divides n ...

1. ## elem. # theo - gcd(a, a+n) divides n ...

OK: "Prove that, for a positive integer n and any integer a, gcd(a, a+n) divides n; hence, gcd(a, a+1) = 1."

starters: "HENCE"??? is that essentially the "therefore, by the given gcd(a, a+n) divides n, then gcd(a, a+1) must equal 1"???
Or are we supposed to prove the gcd(a, a+n) part?

Either way, where do I start?

2. Originally Posted by cassiopeia1289
OK: "Prove that, for a positive integer n and any integer a, gcd(a, a+n) divides n; hence, gcd(a, a+1) = 1."
Let $d=\gcd(a,a+n)$. Therefore, $d|a$ and $d|(a+n)$. Therefore, $d|[(a+n) - a] \implies d|n$.

3. Ok, yeah thanks but didn't really answer my question.
Are we trying to prove gcd(a, a+1) = 1 as the end result?

4. Originally Posted by cassiopeia1289
Ok, yeah thanks but didn't really answer my question.
Are we trying to prove gcd(a, a+1) = 1 as the end result?
That does answer your question. Because if $d=\gcd(a,a+1)$ then $d|1 \implies d= 1$ (by above).

5. ah ok, so the answer would be: yes! it is asking you to prove that gcd(a,a+1)=1!
(sorry, its just, I didn't really want like the whole think figured out for me, I wanted to learn and do the work, but needed just a little nudge in the right direction as to what the question is actually asking and where to start - but still thanks, though)