# Re: Greatest common denominator

*From*: magidin@xxxxxxxxxxxxxxxxx (Arturo Magidin)*Date*: Tue, 27 Nov 2007 19:56:58 +0000 (UTC)

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

.

**Follow-Ups**:**Re: Greatest common denominator***From:*marksmith

**References**:**Greatest common denominator***From:*marksmith

- Prev by Date:
**Re: The infintely small number b** - Next by Date:
**Re: Riemann Zeta Function** - Previous by thread:
**Re: Greatest common denominator** - Next by thread:
**Re: Greatest common denominator** - Index(es):