Modular Arithmetic & Number Theory

In summary, the conversation discusses a mathematical proof regarding the prime divisors of 2^k + 1. The hint suggests using proof by contradiction to show that k has no prime divisors other than 2. Through the use of logic and algebraic equations, the proof is completed and it is shown that k can only have prime divisors of 2. The conversation also touches on the importance of independent thinking and problem-solving skills.
  • #1
1,270
0
1) Suppose 2^k + 1 is a prime number. Prove that k has no prime divisors other than 2.
(Hint: if k=ab with b odd, consider 2^k + 1 modulo 2^a +1)


First of all, I have a little question.
k=ab with b odd. Is this always possible for any natural number k? Why?

Assuming it's always possible:
(I am using ...=... (mod ..) to mean congruence)

2^k = (2^a)^b =(-1)^b = -1 (mod 2^a + 1) since b is odd

=> 2^k + 1 = 0 (mod 2^a +1)

=> 2^k +1 is divisible by 2^a +1

=> 2^a +1 = 1 OR 2^a +1 = 2^k +1 (since 2^k +1 is a prime)

=> 2^a = 0 OR 2^a = 2^ k

And I am stuck here, what's next?

Thank you!
 
Last edited:
Physics news on Phys.org
  • #2
Little question first. No, it's not possible for any k except in the trivial sense that 1 is odd. The hint is suggesting you use proof by contradiction. Assume k has a prime factor that's not 2. Let b be that factor.
 
  • #3
OK, now I understand the logic of the question, but the work-out still seems to be the same and I am stuck at the same point...
 
  • #4
Great. So why did you just pass over "=> 2^k +1 is divisible by 2^a +1" in your relentless drive to a state of confusion? 2^k+1 is assumed to be PRIME. Didn't that make you think, even for a second? DO YOU UNDERSTAND WHY GIVING ADVICE CAN GET FRUSTRATING??
 
  • #5
I really think you are just sleeping while you write these lines. Thinking, "I don't have to think, somebody else will do it for me". I'll just get confused. And ask again, and again and again. You are missing REALLY OBVIOUS POINTS. And don't tell me how badly prepared your curriculum is or how bad the level of instruction. PF is making you intellectually lazy. You might want to lay off the posting for a while and just try a few questions on your own.
 
  • #6
I think there is some delay in displaying my edited version, that's not where I got stuck, I am stuck at "...2^a = 0 OR 2^a = 2^k"

2^a=0 is contradiction
2^a=2^k => a=k. But k=ab => ab=a but b is prime => contradiction

=> k has no prime divisors other than 2 => done!

This is not obvious to me!
And I am doing hundreds of practice problems this week, and I am only stuck on a few and post it here to see if someone can help! I am not lazy...
 
Last edited:
  • #7
kingwinner said:
I think there is some delay in displaying my edited version, that's not where I got stuck, I am stuck at "...2^a = 0 OR 2^a = 2^k"

2^a=0 is contradiction
2^a=2^k => a=k. But k=ab => ab=a but b is prime => contradiction

=> k has no prime divisors other than 2 => done!

This is not obvious to me!
And I am doing hundreds of practice problems this week, and I am only stuck on a few and post it here to see if someone can help! I am not lazy...

I didn't mean you were lazy. I meant you are overdependent on getting a hint before you start thinking. The above looks fine. it's obvious to you now, right?
 

1. What is modular arithmetic?

Modular arithmetic is a branch of mathematics that deals with integers and their remainders after division by a fixed number, called the modulus. It has applications in various fields such as computer science, cryptography, and engineering.

2. How is modular arithmetic different from regular arithmetic?

Unlike regular arithmetic, where numbers continue to increase as we add or multiply, modular arithmetic operates within a finite set of numbers. This means that after a certain point, the numbers start repeating in a cyclical pattern. Additionally, in modular arithmetic, division is not always possible, and the result is not necessarily unique.

3. What is the Chinese Remainder Theorem in number theory?

The Chinese Remainder Theorem is a fundamental theorem in number theory that states that if we have a system of linear congruences with pairwise relatively prime moduli, then there exists a unique solution to the system of congruences. This theorem has many practical applications, such as in cryptography and solving systems of equations.

4. What is Euler's totient function and how is it used in number theory?

Euler's totient function, also known as Euler's phi function, is a number theory function that counts the positive integers less than or equal to a given number that are relatively prime to that number. It has applications in cryptography, particularly in the RSA algorithm, and in understanding the properties of prime numbers.

5. How is number theory used in cryptography?

Number theory plays a crucial role in modern cryptography, particularly in creating and breaking encryption algorithms. Techniques such as modular arithmetic, prime factorization, and the Chinese Remainder Theorem are used to develop secure encryption methods. Additionally, concepts such as Euler's totient function and the discrete logarithm problem are used in public-key cryptography.

Suggested for: Modular Arithmetic & Number Theory

Back
Top