Ma · Mathematics

What Is the Highest Common Factor of n and 2n + 1?

Published By the 9to5Science editorial team

At a glance

  1. 1. Take a common divisor

    Let d be any integer that divides both n and 2n + 1.

  2. 2. Subtract a multiple

    Since d divides both terms, it also divides their difference, (2n + 1) − 2n = 1.

  3. 3. Identify the gcd

    The only positive divisor of 1 is 1, so the greatest common divisor is 1.

Advertisement

For every integer nn, the highest common factor (also called the greatest common divisor) of nn and 2n+12n+1 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 nn is positive, zero, or negative. In the usual convention, a gcd is nonnegative, and gcd⁡(0,1)=1\gcd(0,1)=1.

The common-divisor argument

Suppose dd is a common divisor of nn and 2n+12n+1. Then there are integers aa and bb such that n=dan=da and 2n+1=db2n+1=db. Subtracting twice the first equality from the second gives

(2n+1)−2n=db−2da=d(b−2a).(2n+1)-2n = db-2da = d(b-2a).

The left-hand side is 1, so dd divides 1. The only positive divisor of 1 is 1. Thus no common divisor greater than 1 exists, and

gcd⁡(n,2n+1)=1.\gcd(n,2n+1)=1.

You can also express the same proof using the gcd identity

gcd⁡(a,b)=gcd⁡(a,b−ka),\gcd(a,b)=\gcd(a,b-ka),

which holds for integers a,b,ka,b,k. Taking a=na=n, b=2n+1b=2n+1, and k=2k=2 gives

gcd⁡(n,2n+1)=gcd⁡(n,1)=1.\gcd(n,2n+1)=\gcd(n,1)=1.

The identity works because a number divides both aa and bb exactly when it divides both aa and b−kab-ka. Subtracting a multiple changes the pair of numbers but not its common divisors.

A worked example

Take n=12n=12. The two numbers are

12and2(12)+1=25.12 \quad\text{and}\quad 2(12)+1=25.

Their difference after subtracting twice 12 from 25 is

25−2(12)=1.25-2(12)=1.

A common divisor of 12 and 25 would have to divide 1, so the only positive common divisor is 1. Hence gcd⁡(12,25)=1\gcd(12,25)=1.

The same reasoning handles a negative value. If n=−4n=-4, then 2n+1=−72n+1=-7, and

(−7)−2(−4)=1.(-7)-2(-4)=1.

Therefore gcd⁡(−4,−7)=1\gcd(-4,-7)=1 under the standard convention that the gcd is nonnegative. For n=0n=0, the pair is 0 and 1, and gcd⁡(0,1)=1\gcd(0,1)=1 as well.

A useful generalization

The calculation is an instance of a broader rule:

gcd⁡(n,kn+r)=gcd⁡(n,r)\gcd(n,kn+r)=\gcd(n,r)

for integers kk and rr. To see why, subtract kk copies of nn from kn+rkn+r; the remainder is rr. In this problem, k=2k=2 and r=1r=1, so the gcd reduces to gcd⁡(n,1)\gcd(n,1), which must be 1.

More generally, if two integers are related by b=ka+rb=ka+r, their gcd is determined by the remainder rr, not by the multiple kaka. 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 nn and 2n+12n+1. The subtraction proves the result directly.
  • Assuming the numbers must be prime. They need not be. For example, with n=10n=10, the numbers are 10 and 21; both are composite, but their gcd is 1.
  • Using the wrong subtraction. The useful operation is (2n+1)−2n(2n+1)-2n, which gives 1. Subtracting nn just once gives n+1n+1, which does not by itself establish the result.
  • Forgetting the sign convention. If nn 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 nn: the two expressions nn and 2n+12n+1 are always relatively prime because their difference from twice nn is 1.

References

  1. 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.