Purchase Solution

Divisors and relative primes

Not what you're looking for?

Ask Custom Question

Let a be an integer. Prove that 2a + 1 and a^2+ 1 are relatively prime.
( relative primes are numbers that their largest common divisor is 1).

a. mistake
b. something is unclear
c. proof is correct, but solved incorrectly (does not follow instructions) Exm. Instruction says proof by induction, but instead solution is a proof by contradiction.

Please use words to describe your proof.


Let a be an integer. Prove that 2a + 1 and + 1 are relatively prime.

Notation: a | b means "a divides b" (evenly) It is understood that a <= b

To prove this, we need a lemma (sub-proof).

if d | a and d | b then d | (a + b)

If d | a then a = kd. Similarly b = md

a + b = kd + md = (k + m)d = nd

Since a + b is a multiple of d then d | (a + b)

In English

d | a means that a is a multiple of d, so we write it as in integer multiple of d

When adding the two, we notice that d factors out from both terms and k + m is another integer n.

The last line reverses the step that we made in the first.

Corollary (which we will actually use)

(If one of the two terms is divisible by d but the other is not, then there sum is not divisible by d.)

Proof by contradiction

The first line assumes that d does not divide into a but does divide into b and a + b. We apply the definition to d | b and d | (a + b) and manipulate algebraically to get a=md. Therefore d | a. But we stated beforehand that d does not divide into a, hence a contradiction (Symbolically represented by the opposing arrows). Since we made the original statement that d | (a + b) and we reached a contradiction, then we know that our assertion was false.

Definition: Two numbers are said to be relatively prime if they do not have any common factors. Example 8=2*2*2 and 15=3*5 are relatively prime

The actual proof.

First, we note that

Let , d is prime > 2 (2a+1 is an odd number and hence not divisible by 2). If we can show that then we have proven that they are relatively prime because any d that divides into 2a+1 will not divide into 4a2 + 1 and therefore have no common factors other than 1.

But because d > 2 and by definition, d | a implies that d < a, therefore and by our corollary,

Purchase this Solution

Solution Summary

The solution provides two short and elegant proofs. Divisors and relative prime functions are provided.

Solution Preview

See Attached

Let's assume that k and that k is a divisor of both and such that:

Where p and q are integers.


Since p and q(2a-1) are integers, the only way the last equation can be true is if k value is either 1 or ...

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.

Probability Quiz

Some questions on probability

Graphs and Functions

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

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Solving quadratic inequalities

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