Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Divisibility and the Euclidean algorithm

Divisibility and the Euclidean algorithm

1.[1p]

Use Euclid's algorithm to find gcd(3587,1071).

CorrectNot quite: 17

2.[1p]

The division algorithm writes -45=7q+r with 0≤r<7. What is r?

CorrectNot quite: 4

3.[2p]

How many divisions does Euclid's algorithm take to find gcd(233,144), counting the last one, which leaves remainder 0?

CorrectNot quite: 11

4.[2p]

Euclid's algorithm on a pair a>b>0 takes 12 divisions. By Lamé's theorem, what is the smallest b can be?

CorrectNot quite: 233

5.[3p]

Find the integer x with 0<x<100 for which 143x+100y=1 has an integer solution y.

CorrectNot quite: 7

6.[2p]

What is the largest value gcd(n+5,3n+2) takes over all positive integers n?

CorrectNot quite: 13

7.[2p]

Why is gcd(a,b)=gcd(b,amodb)?

Correct
The answer is: $a$ and $b$ have exactly the same common divisors as $b$ and $a \bmod b$
The answer is: $a$ and $b$ have exactly the same common divisors as $b$ and $a \bmod b$
The answer is: $a$ and $b$ have exactly the same common divisors as $b$ and $a \bmod b$

8.[2p]

Since gcd(252,198)=18, for which values of c does 252x+198y=c have integer solutions?

Select all that apply

Correct
Correct
Correct
The answer is: $18$, $36$, $-54$
The answer is: $18$, $36$, $-54$
The answer is: $18$, $36$, $-54$

9.[3p]

Match each result to what it says or how it is proved.

  • The division algorithm

  • Euclid's algorithm

  • Lamé's theorem

  • Bézout's identity

  • Book VII of the Elements, around 300 BC

  • consecutive Fibonacci numbers are the worst case

  • the gcd is a combination ax+by

  • proved from the well-ordering principle

Show the answer

The division algorithm: proved from the well-ordering principle Euclid's algorithm: Book VII of the Elements, around 300 BC Lamé's theorem: consecutive Fibonacci numbers are the worst case Bézout's identity: the gcd is a combination ax+by