# Evaluating the greatest common divisor of pairs $(a, a^2)$, $(a, a+1)$, $(a, a+2)$

I have a homework question which i'm struggling with, i would be interested in what method i should use to solve the following problems:

> Let a be a positive integer. Evaluate the following:
> (i) gcd(a,a^2)
> (ii) gcd(a,a+1)
> (iii) gcd(a,a+2)
> (you do not need the Euclidean Algorithm to answer these questions.)


Im not looking for the answers to these questions rather the approach i should take to solving them and problems like them? I've searched and while i can find links to solving gcd's they all seem to be of the style gcd(2,4) etc.

Thanks for the help (i know its probably very simple.)

Hint: Pick some numbers for $a$ such as $a=5$. Now, what would divide both 5 and 25? Or for the second one, what would divide both 5 and 6? How about 5 and 7 for the third one? Also, for the third one, what if $a=6$ and we tried to find the gcd of 6 and 8?

• Thanks Paul, yes I understand that for I): a is the gcd. and for ii): it is 1. and for iii): it is dependent on whether a is odd or even. However how do I show this is true? I couldn't just show examples as a could be any integer? – MapReduceFilter Aug 8 '14 at 0:57
• No, if they want $a$ to be a variable, then you would have to argue in general. The first one should be simple since anything larger than $a$ wouldn't divide $a$. For the second and third, if something divides $a$ and divides the sum of $a$ and something else then it would have to divide the something else too, right? Could you "up vote" my answer? – Paul Sundheim Aug 8 '14 at 1:07

Hint $\ \gcd(a,\,b) = \gcd(a,\,b-a) = \gcd(a,\,b-2a) = \,\cdots\, = \gcd(a,\,b\ {\rm mod}\ a)\$ tackles all three.

i.) We need the largest integer $k$ such that $k \; | \;a$ and $k \; | \; a^2 = a(a)$ (the $|$ symbol means "divides".) Clearly, the largest integer is $k = a$.

i) let d=gcd(a,a^2) then ther exist integers x and y such that ax + a^2 y=d =>a(x+a^2 y)=d in other words a|d and we have d|a by definition which forces a=d .

ii) d|a+1-a => d|1 so d=1

!!!) d|a+2-a => d|2 so d=1 or d=2