3^n+1 has an odd prime divisor

  • Thread starter Thread starter wsldam
  • Start date Start date
  • Tags Tags
    Prime
AI Thread Summary
The discussion centers on proving that 3n + 1 has an odd prime divisor for all natural numbers greater than 1. Participants suggest exploring specific values of 3n + 1, such as 32 + 1, 33 + 1, and 34 + 1, to identify patterns. There is a mention that 3n + 1 cannot be an odd prime and that it can be analyzed using modular arithmetic, specifically modulo 8. Additionally, approaches include considering cases for odd and even values of n. The conversation emphasizes the importance of hints rather than complete solutions for tackling the proof.
wsldam
Messages
1
Reaction score
0
Prove that 3n + 1 has an odd prime divisor for all natural numbers > 1. I tried using order but it didn't really get me anywhere. Would prefer hints rather than complete solutions. Thanks.
 
Physics news on Phys.org
If you can't see how to prove this sort of result, start by playing around with the numbers.

Work out the values of a few numbers, 32+1, 33+1, 34+1, ... What do you notice about them?
 
welcome to pf!

hi wsldam! welcome to pf! :smile:
wsldam said:
Prove that 3n + 1 has an odd prime divisor for all natural numbers > 1.

isn't that another way of saying that 2m can never be of the form 3n + 1 ?
 


tiny-tim said:
hi wsldam! welcome to pf! :smile:


isn't that another way of saying that 2m can never be of the form 3n + 1 ?

It is also saying that 3n + 1 is never an odd prime (but that's easy to show).
 
solution 1: Do it modulo 8
solution 2: Do it for m odd (mod 3) and m even (factor 2m-1).
 
nice! :smile:
 

Similar threads

For ## n>1 ##, show that every prime divisor of ## n+1 ## is an odd integer
Replies
9
Views
2K
Prove that there are infinitely many primes of the form ## 6k+1 ##?
Replies
12
Views
3K
Prove that there exists a prime with at least ## n ## of its digits.
Replies
2
Views
2K
Prime factors of a unique form in the each term a sequence?
Replies
2
Views
2K
A Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
Replies
10
Views
2K
MHB Is $p$ a prime divisor of $\phi(n)$ if $G$ has an element of order $n$?
Replies
1
Views
3K
Show that the primes of the form 4n-1 and 4n +1 are infinite
Replies
2
Views
12K
Proof about product of 4 integers
Replies
6
Views
2K
Prime numbers and divisibility by 12
Replies
5
Views
2K
Carmichael Numbers: Prove Product of Primes is a Carmichael Number
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top