1
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – MapReduceFilter Aug 8 '14 at 0:57
  • 1
    $\begingroup$ 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? $\endgroup$ – Paul Sundheim Aug 8 '14 at 1:07
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.