# Number TheoryShow that 15|2^{4n}-1

#### evinda

##### Well-known member
MHB Site Helper
Hey!!! I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey!!! I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? Hai! What is $2^{4n}-1 \pmod 3$?
And $2^{4n}-1 \pmod 5$?

#### evinda

##### Well-known member
MHB Site Helper
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$?? #### Klaas van Aarsen

##### MHB Seeker
Staff member
$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$?? Yep! #### evinda

##### Well-known member
MHB Site Helper
Yep! Great!!!Thank you very much!!! #### Prove It

##### Well-known member
MHB Math Helper
Hey!!! I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? 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
Alternatively:
$$2^{4n}-1 \equiv (2^4)^n -1 \equiv 16^n - 1 \equiv 1^n - 1 \equiv 0 \pmod{15}$$
$\blacksquare$