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

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
To show that 15 divides \(2^{4n} - 1\), it is necessary to demonstrate that \(2^{4n} - 1 \equiv 0 \pmod{3}\) and \(2^{4n} - 1 \equiv 0 \pmod{5}\). Both conditions hold true, confirming that \(15\) divides \(2^{4n} - 1\). A proof by induction can be employed, starting with the base case \(n=1\), where \(2^{4 \cdot 1} - 1 = 15\). The inductive step shows that if the statement holds for \(n=k\), it also holds for \(n=k+1\), thus concluding that \(15 | (2^{4n} - 1)\) for all natural numbers \(n\). The alternative approach using modular arithmetic also confirms the result.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hey! :o
I am given the following exercise: Show that $$15|2^{4n}-1$$
How can I do this?? :confused:
 
Mathematics news on Phys.org
evinda said:
Hey! :o
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$?
 
I like Serena said:
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$?? :confused:
 
evinda said:
$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$?? :confused:

Yep! :D
 
I like Serena said:
Yep! :D

Great!Thank you very much! (Yes)
 
evinda said:
Hey! :o
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:
Alternatively:
$$2^{4n}-1 \equiv (2^4)^n -1 \equiv 16^n - 1 \equiv 1^n - 1 \equiv 0 \pmod{15}$$
$\blacksquare$
 

Similar threads

Back
Top