Question

14. Assume that n is a nonnegative integer .

a . Find gcd ( 2n + 1 , n )

Answer 1

You could use the Eucledean algorithm, where you actually would get the "last line" of the algorithm straight up which shows that the "last nonzero remainder" is 1, so the GCD is 1. For gcd(2n+1,n)

2n+1=2·n+1
n=1·n+0.

Say you would like to find gcd(30,7), according to the algorithm you would write:

30=7·4+2
7=3·2+1
3=3·1+0

In the last row the remaider is 0
so the last nonzero remainder is 1 therefore gcd(30,7)=1

Say you would like to find gcd(40,12)

then you would write

40=3·12+4
12=3·4+0

The last nonzero remainder is 4
therefore gcd(40,12)=4