My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree12Thanks
Reply
 
LinkBack Thread Tools Display Modes
December 9th, 2016, 02:48 PM   #1
Senior Member
 
Joined: Jan 2013
From: Italy

Posts: 153
Thanks: 7

verify by induction that $5^{2n} - 1$ is divisible by 24.

Hi,

I have done this exercise and kindly I would want to receive some possible corrections and suggestions!

Also I have looked at the Peano Postulates or Axioms:
Quote:
Let there exists a non-empty set $\mathbb{N}$ such that
Postulate I: $1 \in \mathbb{N}$;
Postulate II: For each $n \in \mathbb{N}$ there exists a unique $n^{*} \in \mathbb{N}$, called the successor of n;
Postulate III: For each $n \in \mathbb{N}$ we have $n^* \ne 1$;
Postulate IV: If $m,n \in \mathbb{N}$ and $m^* = n^*$, then $m = n$;
Postulate V: Any subset $K$ of $\mathbb{N}$ having the properties
(a) $1 \in K$
(b) $k^* \in K$ whenever $k \in K$
is equal to $\mathbb{N}$.

Exercise:
Using the principle of mathematical induction, check the truth of
$24 | 5^{2n} - 1$
for each $n \in \mathbb{N}$


My own development:
$P(n) : 5^{2n} - 1$ is divisible by 24, for each $n \in \mathbb{N}$

Consider a set $K = \left \{ k : k \in \mathbb{N}, P(k) \mbox{ is true } \right \}$ i.e. a set $K$ containing all the $k$ numbers that makes $P(n)$ true when $n=k$

Consider $1 \in \mathbb{N}$ for the first Peano Axiom.
Let's check if $P(n)$ is true for $n=1$. If so, $1$ will be an element to include in the set $K$ defined above:
$P(1) : 5^{2(1)} - 1 = \\
= 5^2 - 1 = \\
= 25 - 1 = \\
= 24$
is divisible by $24$.

And the value $24$ we just obtained, is divisible by $24$ .
so $P(1)$ seems to be true!
Therefore we have $1 \in K$. And the Postulate V (a) is fulfilled.

Consider now, $k$ any other element in $K$, we suppose that is true the following proposition:
$P(k) : 5^{2k} - 1$ is divisible by $24$ for each $k \in \mathbb{N}$
we want to know if also the successor of $k$, will be in $K$.

So we consider $k^{*}$ as the successor of $k$. We want to check the truth of:
$P(k^{*}) : 5^{2k^{*}} - 1$ is divisible by $24$, for each $k \in \mathbb{N}$

for one definition of addition in $\mathbb{N}$ we have that
$k + 1 = k^{*}$
i.e. the successor of a number is that number added with $1$

so going to substituting we obtain:
$P(k+1) : 5^{2(k+1)} - 1 = \\
= 5^{2k + 2} - 1 = \\
= 5^{2k} \cdot 5^{2} - 1 = \\
= 5^{2k} \cdot 25 - 1 = \\
= 5^{2k} \cdot (24 + 1) - 1 = \\
= ( 5^{2k} \cdot 24 ) + (5^{2k} - 1),$
is divisible by $24$.

We can see that $( 5^{2k} \cdot 24 )$ is divisible by $24$,
and also $(5^{2k} - 1)$ is is divisible by $24$ by inductive hypotesis,
hence $( 5^{2k} \cdot 24 ) + (5^{2k} - 1)$ is divisible by $24$.
So $P(k+1)$ is true.

Since also $k^{*} \in K$, for each $k \in \mathbb{N}$, the Postulate V (b) is fulfilled. It follows that $K = \mathbb{N}$, the Postulate V is fullfilled, and the proposition is valid for every $n \in \mathbb{N}$


What do you think about it?
Many thanks!
beesee is offline  
 
December 9th, 2016, 03:04 PM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: Southern California, USA

Posts: 1,498
Thanks: 755

I think you can make it about a fifth of its length.
You can assume your audience understands how induction works.

$P_1: 5^2 - 1 \pmod{24} = (25-1)\pmod{24}= 24\pmod{24}=0$

$P_1 =True$

$5^{2(n+1)}-1 = 5^2(5^{2n})-1$

We assume $P_n$ so

$ 5^2(5^{2n})-1 = 5^2(24k+1)-1 = (25)(24)k + 25-1 = (25k+1)(24)$

$(25k+1)(24) \pmod{24} = 0$

so $P_{n+1} = True$

QED
Thanks from beesee and topsquark

Last edited by skipjack; December 13th, 2016 at 02:07 AM.
romsek is online now  
December 9th, 2016, 03:50 PM   #3
Senior Member
 
Joined: Jan 2013
From: Italy

Posts: 153
Thanks: 7

Yes it's clear thanks!

Quote:
Originally Posted by romsek View Post
You can assume your audience understands how induction works.
Yes, but, I want to share this topic with step by step passages, also with beginner people that now starts to understand how induction works! (like me).
Thanks from topsquark and SenatorArmstrong
beesee is offline  
December 9th, 2016, 04:28 PM   #4
Math Team
 
topsquark's Avatar
 
Joined: May 2013
From: The Astral plane

Posts: 1,595
Thanks: 620

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
Originally Posted by beesee View Post
Yes it's clear thanks!



Yes, but, I want to share this topic with step by step passages, also with beginner people that now starts to understand how induction works! (like me).
And I, for one, am glad you did. I've never seen it broken down like that.

-Dan
Thanks from beesee and SenatorArmstrong
topsquark is online now  
December 9th, 2016, 07:42 PM   #5
Member
 
Joined: Oct 2016
From: Melbourne

Posts: 77
Thanks: 35

My method:

The statement "24 divides $\displaystyle \begin{align*} 5^{2\,n} - 1 \end{align*}$ for all $\displaystyle \begin{align*} n \in \mathbf{N} \end{align*}$" is equivalent to "$\displaystyle \begin{align*} 5^{2\,n} - 1 = 24\,p \end{align*}$ where $\displaystyle \begin{align*} n, p \in \mathbf{N} \end{align*}$".

Base Step:

$\displaystyle \begin{align*} 5^{2 \cdot 1} - 1 &= 5^2 - 1 \\ &= 25 - 1 \\ &= 24 \\ &= 24 \cdot 1 \end{align*}$

The base step is true.

Inductive Step:

Assume that $\displaystyle \begin{align*} 5^{2\,k} - 1 = 24\,m \end{align*}$ is a true statement for some $\displaystyle \begin{align*} k, m \in \mathbf{N} \end{align*}$. Then

$\displaystyle \begin{align*} 5^{2\,\left( k + 1 \right) } - 1 &= 5^{2\,k + 2} - 1 \\ &= 5^{2\,k} \cdot 5^2 - 1 \\ &= 25 \cdot 5^{2\,k} - 1 \\ &= 24 \cdot 5^{2\,k} + 5^{2\,k} - 1 \\ &= 24 \cdot 5^{2\,k} + 24\,m \\ &= 24 \,\left( 5^{2\,k} + m \right) \\ &= 24\,p \textrm{ where } p = 5^{2\,k} + m \end{align*}$

The inductive step is true.

Thus we have proved that 24 divides $\displaystyle \begin{align*} 5^{2\,n} - 1 \end{align*}$ for all $\displaystyle \begin{align*} n \in \mathbf{N} \end{align*}$.
Thanks from beesee
Prove It is offline  
December 10th, 2016, 05:08 PM   #6
Senior Member
 
Joined: Dec 2015
From: Earth

Posts: 156
Thanks: 21

$\displaystyle 5^{2n} -1=25^n-1=25^n-1^n=24(25^{n-1}+25^{n-2}+....+1)$
$\displaystyle 24|24(25^{n-1}+25^{n-2}+....+1)$
Thanks from beesee and topsquark
idontknow is offline  
December 13th, 2016, 01:15 AM   #7
Senior Member
 
Joined: Jan 2013
From: Italy

Posts: 153
Thanks: 7

Quote:
Originally Posted by idontknow View Post
$\displaystyle =25^n-1^n=24(25^{n-1}+25^{n-2}+....+1)$
please can you explain me better what are the calculations used between these two passages? Thanks!
beesee is offline  
December 13th, 2016, 02:15 AM   #8
Global Moderator
 
Joined: Dec 2006

Posts: 18,053
Thanks: 1395

Quote:
Originally Posted by beesee View Post
What do you think about it?
It contains various slips. For example, your reference to "any other element" is inappropriate (as you intend to show that such an element exists, you shouldn't assume it does).
skipjack is offline  
December 13th, 2016, 05:20 AM   #9
Member
 
Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

I was taught a slightly different but easier way.


If (base case) 5^(2(1)) - 1 = 24,

5^(2n) - 1 = 24m, m,n E N

---> 5^(2n+2) - 1 = 24p = 25*5^(2n) - 1 = 25(24m + 1) - 1, p E N

Then 5^(2n) - 1 = 24m


That should be all you need, except maybe add a little more work to show that 24p = 25(24m + 1) - 1 = 25*24m + 24, which is just trivial arithmetic.
Mathbound is offline  
December 13th, 2016, 05:37 AM   #10
Global Moderator
 
Joined: Dec 2006

Posts: 18,053
Thanks: 1395

Quote:
Originally Posted by beesee View Post
can you explain the calculations used between these two passages?
This relates to a direct method, not one that uses mathematical induction.
To understand it, expand $(25 - 1)(25^{n-1} + 25^{n-2} + \,.\,.\,. + 1)$.
skipjack is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
$52n, divisible, induction, verify



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
ABC is a three digit number. If ABC is divisible by 3, is CBA divisible by 3? Tangeton Number Theory 5 April 13th, 2016 12:01 PM
Mathematical Induction (Prove function is always divisible by 36) prismo69 Applied Math 2 March 14th, 2015 08:52 PM
Induction: prove n^5-n is divisible by 5 for all n in N. king.oslo Algebra 11 June 24th, 2013 01:46 AM
Verify the following Rakshasa Applied Math 7 May 7th, 2012 01:37 PM
Prove that (11^n) - 6 is divisible by 5 (use induction) usermind Applied Math 7 May 1st, 2010 04:18 PM





Copyright © 2017 My Math Forum. All rights reserved.