Proof about relatively prime integers.

In summary, the conversation discusses the proof that if n is a positive odd integer and k is a positive integer, then n and n+2^k are relatively prime. The conversation also mentions the importance of providing a detailed prime decomposition for n and the other number in order to fully explain the proof. The proof is based on the fact that if n and n+2^k have a common factor, it should also divide their difference, which is 2^k. However, since n is odd, it has no factors of 2, leading to a contradiction and proving that n and n+2^k are relatively prime.
  • #1
cragar
2,552
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
  • #2
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.
 

Related to Proof about relatively prime integers.

1. What are relatively prime integers?

Relatively prime integers are two numbers that do not have any common factors other than 1. This means that their greatest common divisor (GCD) is 1.

2. How can you prove that two integers are relatively prime?

One way to prove that two integers are relatively prime is to find their GCD. If the GCD is 1, then the integers are relatively prime. Another way is to use the Euclidean algorithm to find the GCD.

3. Are all prime numbers relatively prime?

Yes, all prime numbers are relatively prime because they only have 1 and themselves as factors. Therefore, they do not have any common factors with other numbers, making them relatively prime.

4. Can two even numbers be relatively prime?

No, two even numbers cannot be relatively prime because they both have 2 as a common factor. In order for two numbers to be relatively prime, they must not share any common factors.

5. Why is it important to know if two integers are relatively prime?

Knowing if two integers are relatively prime can be useful in many mathematical applications, such as cryptography and number theory. It also helps in simplifying fractions and finding the inverse of a number in modular arithmetic.

Similar threads

A Prime Number Powers of Integers and Fermat's Last Theorem
    • General Math
Replies
1
Views
805
B Are All Imaginable Integer Series Necessarily Infinite?
    • General Math
Replies
17
Views
651
I Number of Integers (<N) divisible only by one power of 2
    • General Math
Replies
6
Views
834
B Calculating the coprime probability of two integers in a different way
    • General Math
Replies
13
Views
1K
I Proof of Differences of Odd Powers
    • General Math
Replies
11
Views
1K
B Extending the Fundamental Theorem of Arithmetic to the rationals
    • General Math
2
Replies
35
Views
3K
MHB Number of natural numbers that have primitive roots
    • General Math
Replies
5
Views
918
I P-adic Order of Zero: Exploring the Assumption
    • General Math
Replies
4
Views
996
For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer
    • Precalculus Mathematics Homework Help
Replies
9
Views
1K
A The Last Occurrence of any Greatest Prime Factor
    • General Math
Replies
7
Views
1K

Hot Threads

Recent Insights

Back
Top