3^n+1 has an odd prime divisor

  • Thread starter Thread starter wsldam
  • Start date Start date
  • Tags Tags
    Prime
Click For Summary

Homework Help Overview

The problem involves proving that \(3n + 1\) has an odd prime divisor for all natural numbers greater than 1. The discussion centers around number theory and properties of integers.

Discussion Character

  • Exploratory, Assumption checking, Conceptual clarification

Approaches and Questions Raised

  • Participants suggest examining specific values of \(3n + 1\) for various \(n\) to identify patterns. There is a mention of using modular arithmetic as a potential approach. Some participants also question the implications of \(3n + 1\) being even or odd and its relationship to prime numbers.

Discussion Status

The discussion is ongoing, with participants exploring different angles and approaches. Some hints have been provided, such as examining values and considering modular properties, but no consensus or resolution has been reached.

Contextual Notes

Participants express a preference for hints rather than complete solutions, indicating a focus on guiding understanding rather than providing direct answers.

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