- Thread starter
- #1

- Apr 13, 2013

- 3,720

Hey!!!

I am given the following exercise: Show that $$15|2^{4n}-1$$

How can I do this??

I am given the following exercise: Show that $$15|2^{4n}-1$$

How can I do this??

- Thread starter evinda
- Start date

- Thread starter
- #1

- Apr 13, 2013

- 3,720

Hey!!!

I am given the following exercise: Show that $$15|2^{4n}-1$$

How can I do this??

I am given the following exercise: Show that $$15|2^{4n}-1$$

How can I do this??

- Admin
- #2

- Mar 5, 2012

- 8,780

Hai!Hey!!!

I am given the following exercise: Show that $$15|2^{4n}-1$$

How can I do this??

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

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

- Thread starter
- #3

- Apr 13, 2013

- 3,720

$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$??Hai!

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

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

- Admin
- #4

- Mar 5, 2012

- 8,780

Yep!$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$??

- Thread starter
- #5

- Apr 13, 2013

- 3,720

Great!!!Thank you very much!!!Yep!

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*}$.Hey!!!

I am given the following exercise: Show that $$15|2^{4n}-1$$

How can I do this??

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:

- Admin
- #7

- Mar 5, 2012

- 8,780

$$2^{4n}-1 \equiv (2^4)^n -1 \equiv 16^n - 1 \equiv 1^n - 1 \equiv 0 \pmod{15}$$

$\blacksquare$