Welcome to our community

Be a part of something great, join today!

Number Theory Show that 15|2^{4n}-1

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Hey!!! :eek:
I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
Hey!!! :eek:
I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? :confused:
Hai! :)

What is $2^{4n}-1 \pmod 3$?
And $2^{4n}-1 \pmod 5$?
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
Hai! :)

What is $2^{4n}-1 \pmod 3$?
And $2^{4n}-1 \pmod 5$?
$2^{4n}-1 \pmod 3=0 $ and $2^{4n}-1 \pmod 5=0$.So,we have writen $15$ as a product of prime numbers $3 \cdot 5$,so the remainder of the division of $2^{4n}-1$ with both of these prime numbers should be $0$?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
$2^{4n}-1 \pmod 3=0 $ and $2^{4n}-1 \pmod 5=0$.So,we have writen $15$ as a product of prime numbers $3 \cdot 5$,so the remainder of the division of $2^{4n}-1$ with both of these prime numbers should be $0$?? :confused:
Yep! :D
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720

Prove It

Well-known member
MHB Math Helper
Jan 26, 2012
1,403
Hey!!! :eek:
I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? :confused:
I'd probably use induction. To show $\displaystyle \begin{align*} 15 | \left( 2^{4n} - 1 \right) \end{align*}$, that means we have to show $\displaystyle \begin{align*} 2^{4n} - 1 = 15p \end{align*}$, where $\displaystyle \begin{align*} p \in \mathbf{Z} \end{align*}$ for all $\displaystyle \begin{align*} n \in \mathbf{N} \end{align*}$.

Base Step: $\displaystyle \begin{align*} n = 1 \end{align*}$

$\displaystyle \begin{align*} 2^{4 \cdot 1} - 1 &= 16 -1 \\ &= 15 \end{align*}$

Inductive Step: Assume the statement is true for $\displaystyle \begin{align*} n = k \end{align*}$, so $\displaystyle \begin{align*} 2^{4k} - 1 = 15m \end{align*}$. Use this to show the statement is true for $\displaystyle \begin{align*} n = k + 1 \end{align*}$, in other words, show that $\displaystyle \begin{align*} 2^{4 \left( k + 1 \right) } - 1 = 15p \end{align*}$ where $\displaystyle \begin{align*} p \in \mathbf{Z} \end{align*}$.

$\displaystyle \begin{align*} 2^{4 \left( k + 1 \right) } - 1 &= 2^{4k + 4} - 1 \\ &= 2^4 \cdot 2^{4k} - 1 \\ &= 16 \cdot 2^{4k} - 1 \\ &= 16\cdot 2^{4k} - 16 + 15 \\ &= 16 \left( 2^{4k} - 1 \right) + 15 \\ &= 16 \cdot 15m + 15 \\ &= 15 \left( 16m + 1 \right) \\ &= 15p \textrm{ where } p = 16m + 1 \in \mathbf{Z} \end{align*}$

Therefore $\displaystyle \begin{align*} 15 | \left( 2^{4k} - 1 \right) \end{align*}$.

Q.E.D.
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
Alternatively:
$$2^{4n}-1 \equiv (2^4)^n -1 \equiv 16^n - 1 \equiv 1^n - 1 \equiv 0 \pmod{15}$$
$\blacksquare$