Proof about relatively prime integers.

  • Context: Graduate 
  • Thread starter Thread starter cragar
  • Start date Start date
  • Tags Tags
    Integers Prime Proof
Click For Summary
SUMMARY

If n is a positive odd integer, then n and n + 2k are relatively prime for any positive integer k. The proof relies on the assumption that n and n + 2k share a common factor, which leads to a contradiction since their difference, 2k, cannot have any factors of 2 due to n being odd. This establishes that n and n + 2k are indeed relatively prime integers.

PREREQUISITES
  • Understanding of odd and even integers
  • Basic knowledge of prime factorization
  • Familiarity with the concept of common factors
  • Experience with proof by contradiction
NEXT STEPS
  • Study the properties of prime numbers and their distributions
  • Learn about proof techniques in number theory
  • Explore the concept of relatively prime integers in greater depth
  • Investigate advanced topics in integer factorization
USEFUL FOR

Mathematicians, students studying number theory, and anyone interested in proofs involving prime integers and their properties.

cragar
Messages
2,546
Reaction score
3
This is not homework. If n is a positive odd integer then
n and [itex]n+2^k[/itex] are relatively prime. k is a positive integer.
Let's assume for contradiction that n and [itex]n+2^k[/itex] have a common factor.
then it should divide their difference but their difference is [itex]2^k[/itex] and since n is odd it has no factors of 2 so this is a contradiction and they are relatively prime.
 
Mathematics news on Phys.org
Hey cragar.

I'm not sure exactly what your lecturer expects, but you might want to write down a prime decomposition for n and the other number and show it in detail.

The intuition behind your proof is right but I'm not sure if your lecturer will want more.
 

Similar threads

Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
3K
Graduate Prime Number Powers of Integers and Fermat's Last Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Number of Integers (<N) divisible only by one power of 2
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Proof of Differences of Odd Powers
  • · Replies 11 ·
Replies
11
Views
2K
High School Extending the Fundamental Theorem of Arithmetic to the rationals
  • · Replies 35 ·
2
Replies
35
Views
5K
Graduate The Last Occurrence of any Greatest Prime Factor
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
MHB Number of natural numbers that have primitive roots
  • · Replies 5 ·
Replies
5
Views
2K
For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer
  • · Replies 9 ·
Replies
9
Views
3K