What Is the Highest Common Factor of n and 2n + 1?
At a glance
- 1. Take a common divisor
Let d be any integer that divides both n and 2n + 1.
- 2. Subtract a multiple
Since d divides both terms, it also divides their difference, (2n + 1) − 2n = 1.
- 3. Identify the gcd
The only positive divisor of 1 is 1, so the greatest common divisor is 1.
For every integer , the highest common factor (also called the greatest common divisor) of and is 1. The key observation is that subtracting twice the first number from the second leaves 1. Any number that divides both original numbers must divide this difference too.
This argument works whether is positive, zero, or negative. In the usual convention, a gcd is nonnegative, and .
The common-divisor argument
Suppose is a common divisor of and . Then there are integers and such that and . Subtracting twice the first equality from the second gives
The left-hand side is 1, so divides 1. The only positive divisor of 1 is 1. Thus no common divisor greater than 1 exists, and
You can also express the same proof using the gcd identity
which holds for integers . Taking , , and gives
The identity works because a number divides both and exactly when it divides both and . Subtracting a multiple changes the pair of numbers but not its common divisors.
A worked example
Take . The two numbers are
Their difference after subtracting twice 12 from 25 is
A common divisor of 12 and 25 would have to divide 1, so the only positive common divisor is 1. Hence .
The same reasoning handles a negative value. If , then , and
Therefore under the standard convention that the gcd is nonnegative. For , the pair is 0 and 1, and as well.
A useful generalization
The calculation is an instance of a broader rule:
for integers and . To see why, subtract copies of from ; the remainder is . In this problem, and , so the gcd reduces to , which must be 1.
More generally, if two integers are related by , their gcd is determined by the remainder , not by the multiple . This is the basic reduction step in the Euclidean algorithm. If the remainder is 1, the original numbers are relatively prime. If the remainder is some other number, continue applying the same reduction using Euclidean divisions, choosing each quotient so that the remainder has smaller absolute value than the divisor; the last nonzero remainder is the gcd.
Common mistakes
- Trying to factor both expressions separately. You do not need to find prime factorizations of and . The subtraction proves the result directly.
- Assuming the numbers must be prime. They need not be. For example, with , the numbers are 10 and 21; both are composite, but their gcd is 1.
- Using the wrong subtraction. The useful operation is , which gives 1. Subtracting just once gives , which does not by itself establish the result.
- Forgetting the sign convention. If is negative, the gcd is still defined as a nonnegative number. The common-divisor argument is unchanged, and the gcd remains 1.
So the highest common factor does not depend on the value of : the two expressions and are always relatively prime because their difference from twice is 1.
References
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.