Solve the Math Puzzle: 15|2^(4n)-1

[evinda]

Hey!
I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this??

 

[I like Serena]

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]

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 written $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$??

 

[I like Serena]

$2^{4n}-1 \pmod 3=0 $ and $2^{4n}-1 \pmod 5=0$.So,we have written $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! :D

 

[evinda]

Yep! :D

Great!Thank you very much! (Yes)

 

[Prove It]

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.

 

[I like Serena]

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