My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
  • 2 Post By Maschke
  • 2 Post By skipjack
  • 2 Post By greg1313
Reply
 
LinkBack Thread Tools Display Modes
June 25th, 2017, 04:43 PM   #1
Newbie
 
Joined: Apr 2017
From: Canada

Posts: 28
Thanks: 1

Prove the following:

Prove or provide a counterexample to the following conjecture:

Assuming "p" is an odd integer,
"2^p - 1" will never be divisible by 3

(The MATH function wasn't working for me)

Last edited by Antoniomathgini; June 25th, 2017 at 04:48 PM.
Antoniomathgini is offline  
 
June 25th, 2017, 08:37 PM   #2
Senior Member
 
Joined: Feb 2016
From: Australia

Posts: 1,422
Thanks: 484

Math Focus: Yet to find out.
Quote:
Originally Posted by Antoniomathgini View Post
Assuming $p$ is an odd integer,
$2^p - 1$ will never be divisible by $3$

(The MATH function wasn't working for me)
What do you mean it wasn't working?
Joppy is online now  
June 25th, 2017, 09:09 PM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by Antoniomathgini View Post
Prove or provide a counterexample to the following conjecture:

Assuming "p" is an odd integer,
"2^p - 1" will never be divisible by 3

(The MATH function wasn't working for me)
$2 \equiv -1 \pmod 3$ so any odd power of $2$ must be $-1$ mod $3$. Subtracting one gives a result that's $-2$ mod $3$.

Similarly any even power of $2$ is $1$ mod $3$ and one less than that is divisible by $3$. For example $2^4 = 16$ which is $1$ more than a multiple of $3$.
Thanks from topsquark and Antoniomathgini

Last edited by Maschke; June 25th, 2017 at 09:19 PM.
Maschke is online now  
June 25th, 2017, 11:53 PM   #4
Global Moderator
 
Joined: Dec 2006

Posts: 18,166
Thanks: 1424

As 3 = 4 - 1 divides 4$^{(p - 1)/2}$ - 1 by the factor theorem,
2$^p$ - 1 = 2(4$^{(p-1)/2}$ - 1) + 1 gives a remainder of 1 when divided by 3.
Thanks from topsquark and Antoniomathgini
skipjack is offline  
June 26th, 2017, 07:19 PM   #5
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,642
Thanks: 960

Math Focus: Elementary mathematics and beyond
Either $2^n-1$ or $2^n+1$ is a multiple of $3$. [Clearly, $2^n$ is not a multiple of $3$. This implies that $2^n$ is either one less or one more than a multiple of $3$.]

$$(2^n-1)(2^n+1)=2^{2n}-1$$

$$3x=2^{2n}-1$$

$$6x=2\cdot2^{2n}-2$$

$$6x+1=2^{2n+1}-1$$

$$QED$$
Thanks from topsquark and Antoniomathgini

Last edited by greg1313; July 3rd, 2017 at 01:14 PM.
greg1313 is online now  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
prove



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
please prove :a<b ,and b+1=c Albert.Teng Algebra 8 July 6th, 2013 09:13 AM
Prove that: mosaic Linear Algebra 4 April 18th, 2011 09:38 AM
Goldbach's conjecture (to prove or not to prove) octaveous Number Theory 13 September 23rd, 2010 05:36 AM
prove prove prove. currently dont know where to post qweiop90 Algebra 1 July 31st, 2008 07:27 AM
prove prove prove. currently dont know where to post qweiop90 New Users 1 December 31st, 1969 04:00 PM





Copyright © 2017 My Math Forum. All rights reserved.