# Euclidean Algorithm

Not what you're looking for?

Prove the Euclidean Algorithm:

Let n be a natural

number, and let q be a positive number. Then there exist natural

numbers m, r such that 0 < or = r < q and n=mq+r

Show that m and r exist and are also unique.

**Fix q and induct on n, and note that you can only use rules of addition

##### Purchase this Solution

##### Solution Summary

The expert examines Euclidean Algorithm.

##### Solution Preview

Proof:

Since q is a positive number, then q>=1.

If q = 1, then for any natural number n, we must have n = n*1 = nq. Let m = n, r = 0, then m, q are natural numbers and n = mq + r.

Now we consider q>=2 and make induction on n.

If n = 0, then we can set m = 0, r = 0 and we ...

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

##### Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

##### Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

##### Probability Quiz

Some questions on probability