Re: Greatest common denominator



In article <4cf83e88-3cee-4632-b9c8-515bb54c48f6@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<marksmith@xxxxxxxxxxxxxxxxx> wrote:
Hi all,

I am having trouble with part of a cryptography assignment:

"2 What is gcd (n, n + 1) for two consecutive integers n and n +1?
Show all steps of your answer. 5 marks"

Common sense tells me the answer is 1.

I could list 100 examples. But I'm not sure how to show this in a
general form.

Any ideas?

Any common divisor of x and y must also divide all numbers of the form
ax+by with a and b integers.

In addition, the greatest common divisor is equal to the smallest
positive integer that can be expressed in that form (Euclid's
Theorem).

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.