My Math Forum > Math Divisibility Rules?

 Math General Math Forum - For general math related discussion and news

 May 2nd, 2017, 06:42 PM #1 Newbie   Joined: May 2017 From: Shanghai, China Posts: 1 Thanks: 0 Divisibility Rules? https://brilliant.org/discussions/th...ility-rules-4/ Prove that if x is divisible by 3, then $\displaystyle 2^x - 1$ is divisible by 7
May 2nd, 2017, 11:20 PM   #2
Math Team

Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
 Originally Posted by anush2209 https://brilliant.org/discussions/th...ility-rules-4/ Prove that if x is divisible by 3, then $\displaystyle 2^x - 1$ is divisible by 7
Let $\ \ \ x = 3y \ \ \$ for any positive integer $\ \ y$

Then

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

$2^{3y} - 1 = (2^3)^y - 1$

Factor

$2^{3y} - 1 = (2^3 - 1)[(2^3)^{y- 1} + (2^3)^{y-2} + ... + 1)]$

$2^{3y} - 1 = 7k$

This shows $\ \ \ 2^x - 1 \ \$ (given your condition) is a multiple of $\ 7 \$ therefore divisible by $\ 7$

Last edited by agentredlum; May 2nd, 2017 at 11:22 PM.

 May 2nd, 2017, 11:22 PM #3 Global Moderator   Joined: Dec 2006 Posts: 19,047 Thanks: 1618 The polynomial $y^n - 1$ is divisible by $y - 1$ by the factor theorem. Hence if $y = a^b$ for positive integers $a$ and $b$, $a^b - 1$ divides $y^n - 1$, which is $a^{bn} - 1$. For the given problem, use $a = 2$ and $b = 3$ so that $a^b- 1 = 7$.

 Tags divisibility, rules

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post xboxprot Advanced Statistics 0 December 6th, 2015 12:41 PM Iwishmath Elementary Math 2 May 25th, 2014 08:47 PM greenmess Algebra 4 March 22nd, 2011 01:31 AM greenmess Linear Algebra 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top