S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Wed, 17 Sep 2014 16:34:03 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Wed, 4 Aug 2010 19:26:10 UTC 
Prove that, if n is an arbitrary positive integer then the expression

1^{n} + 2^{n} + 3^{n} + 4^{n} is divisible by 5 iff n is not divisible by 4.

enjoy,

cheers


Top
  
 
PostPosted: Thu, 5 Aug 2010 06:34:46 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6867
Location: On this day Taiwan becomes another Tiananmen under Dictator Ma.
Casdan1 wrote:
Prove that, if n is an arbitrary positive integer then the expression

1^{n} + 2^{n} + 3^{n} + 4^{n} is divisible by 5 iff n is not divisible by 4.

enjoy,

cheers


Spoiler:
Power sum in \mathbb{Z}/p...

It follows immediately from the existence of primitive root: (g^n-1)[1^n+2^n+\dots+(p-1)^n]=0, so when (p-1)\nmid n we must have 1^n+2^n+\dots+(p-1)^n=0, and obviously when (p-1)\mid n we have 1^n+2^n+\dots+(p-1)^n=-1.

_________________
\begin{aligned}
Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\
Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\
Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\
Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\
Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\
Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4
\end{aligned}


Top
 Profile  
 
PostPosted: Thu, 5 Aug 2010 16:16:24 UTC 
outermeasure wrote:
Casdan1 wrote:
Prove that, if n is an arbitrary positive integer then the expression

1^{n} + 2^{n} + 3^{n} + 4^{n} is divisible by 5 iff n is not divisible by 4.

enjoy,

cheers


Spoiler:
Power sum in \mathbb{Z}/p...

It follows immediately from the existence of primitive root: (g^n-1)[1^n+2^n+\dots+(p-1)^n]=0, so when (p-1)\nmid n we must have 1^n+2^n+\dots+(p-1)^n=0, and obviously when (p-1)\mid n we have 1^n+2^n+\dots+(p-1)^n=-1.


Yep you got it.

Below is your solution translated into plain english.

\mbox{1^{4} = 1, 2^4 = 16 = 5*3 + 1, 3^4  = 81 = 5*16 + 1, 4^4 = 256 = 5*51 + 1}

Each of the numbers is of the form \mbox{5k + 1}, where k is an integer.

Also note that if A stands for 1,2,3, or 4 and if l is a positive integer, then A^{4l} is of the form 5k + 1 because A^{4l} - 1 = (A^4)^{l} - 1 = (A^4 - 1)[(A^4)^{l-1} + (A^4)^{l-2} + \ldots + 1] where the first factor on the right is divisible by 5, and the second is an integer.

Any positive integer may be written in the form 4l + r where l is a positive integer or zero, and the remainder r is one of the numbers 0, 1, 2, or 3. In particular the exponent n may be written in this form so that.

S = 1^n + 2^n + 3^n + 4^n
S = 1 + 2^{4l + r} + 3^{4l + r} + 4^{4l + r}
S = 1 + 2^{4l}2^r + 3^{4l}3^r + 4^{4l}4^r
S = 1 + (5k_1 + 1)2^r + (5k_2 + 1)3^r +(5k_3 + 1)4^r
S = 5(k_12^r + k_23^r + k_34^r) + (1 + 2^r + 3^r + 4^r)
S = 5m + R

where m is an integer, and R = 1 + 2^r + 3^r + 4^r.

Thus, S is divisible by 5 iff R is. If n is divisible by 4, then r = 0 and R = 4; in this case S is not divisible by 5. But if n is not divisible by 4, then r = 1, 2, or 3, and the corresponding values of R are 10, 30 or 100; in this case S is divisible by 5.


Top
  
 
PostPosted: Thu, 5 Aug 2010 21:51:16 UTC 
Offline
Moderator
User avatar

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 14036
Location: Austin, TX
Casdan1 wrote:
outermeasure wrote:
Casdan1 wrote:
Prove that, if n is an arbitrary positive integer then the expression

1^{n} + 2^{n} + 3^{n} + 4^{n} is divisible by 5 iff n is not divisible by 4.

enjoy,

cheers


Spoiler:
Power sum in \mathbb{Z}/p...

It follows immediately from the existence of primitive root: (g^n-1)[1^n+2^n+\dots+(p-1)^n]=0, so when (p-1)\nmid n we must have 1^n+2^n+\dots+(p-1)^n=0, and obviously when (p-1)\mid n we have 1^n+2^n+\dots+(p-1)^n=-1.


Yep you got it.

Below is your solution translated into plain english.

\mbox{1^{4} = 1, 2^4 = 16 = 5*3 + 1, 3^4  = 81 = 5*16 + 1, 4^4 = 256 = 5*51 + 1}

Each of the numbers is of the form \mbox{5k + 1}, where k is an integer.

Also note that if A stands for 1,2,3, or 4 and if l is a positive integer, then A^{4l} is of the form 5k + 1 because A^{4l} - 1 = (A^4)^{l} - 1 = (A^4 - 1)[(A^4)^{l-1} + (A^4)^{l-2} + \ldots + 1] where the first factor on the right is divisible by 5, and the second is an integer.

Any positive integer may be written in the form 4l + r where l is a positive integer or zero, and the remainder r is one of the numbers 0, 1, 2, or 3. In particular the exponent n may be written in this form so that.

S = 1^n + 2^n + 3^n + 4^n
S = 1 + 2^{4l + r} + 3^{4l + r} + 4^{4l + r}
S = 1 + 2^{4l}2^r + 3^{4l}3^r + 4^{4l}4^r
S = 1 + (5k_1 + 1)2^r + (5k_2 + 1)3^r +(5k_3 + 1)4^r
S = 5(k_12^r + k_23^r + k_34^r) + (1 + 2^r + 3^r + 4^r)
S = 5m + R

where m is an integer, and R = 1 + 2^r + 3^r + 4^r.

Thus, S is divisible by 5 iff R is. If n is divisible by 4, then r = 0 and R = 4; in this case S is not divisible by 5. But if n is not divisible by 4, then r = 1, 2, or 3, and the corresponding values of R are 10, 30 or 100; in this case S is divisible by 5.


I like outermeasure's way better, it's more transparent.

_________________
(\ /)
(O.o)
(> <)
This is Bunny. Copy Bunny into your signature to help him on his way to world domination


Top
 Profile  
 
PostPosted: Fri, 6 Aug 2010 15:02:17 UTC 
Shadow wrote:
Casdan1 wrote:
outermeasure wrote:
Casdan1 wrote:
Prove that, if n is an arbitrary positive integer then the expression

1^{n} + 2^{n} + 3^{n} + 4^{n} is divisible by 5 iff n is not divisible by 4.

enjoy,

cheers


Spoiler:
Power sum in \mathbb{Z}/p...

It follows immediately from the existence of primitive root: (g^n-1)[1^n+2^n+\dots+(p-1)^n]=0, so when (p-1)\nmid n we must have 1^n+2^n+\dots+(p-1)^n=0, and obviously when (p-1)\mid n we have 1^n+2^n+\dots+(p-1)^n=-1.


Yep you got it.

Below is your solution translated into plain english.

\mbox{1^{4} = 1, 2^4 = 16 = 5*3 + 1, 3^4  = 81 = 5*16 + 1, 4^4 = 256 = 5*51 + 1}

Each of the numbers is of the form \mbox{5k + 1}, where k is an integer.

Also note that if A stands for 1,2,3, or 4 and if l is a positive integer, then A^{4l} is of the form 5k + 1 because A^{4l} - 1 = (A^4)^{l} - 1 = (A^4 - 1)[(A^4)^{l-1} + (A^4)^{l-2} + \ldots + 1] where the first factor on the right is divisible by 5, and the second is an integer.

Any positive integer may be written in the form 4l + r where l is a positive integer or zero, and the remainder r is one of the numbers 0, 1, 2, or 3. In particular the exponent n may be written in this form so that.

S = 1^n + 2^n + 3^n + 4^n
S = 1 + 2^{4l + r} + 3^{4l + r} + 4^{4l + r}
S = 1 + 2^{4l}2^r + 3^{4l}3^r + 4^{4l}4^r
S = 1 + (5k_1 + 1)2^r + (5k_2 + 1)3^r +(5k_3 + 1)4^r
S = 5(k_12^r + k_23^r + k_34^r) + (1 + 2^r + 3^r + 4^r)
S = 5m + R

where m is an integer, and R = 1 + 2^r + 3^r + 4^r.

Thus, S is divisible by 5 iff R is. If n is divisible by 4, then r = 0 and R = 4; in this case S is not divisible by 5. But if n is not divisible by 4, then r = 1, 2, or 3, and the corresponding values of R are 10, 30 or 100; in this case S is divisible by 5.


I like outermeasure's way better, it's more transparent.


Yeah, his solution is very elegant and compact. However, I'm completely lost just by some of his notation and terminology.

I'm a Physicist in training (Grad School), so for me Math is just a tool to use to get what I want.
One day we will be able to peacefully coexist, (Physicists vs. Mathematicians).


Top
  
 
PostPosted: Fri, 6 Aug 2010 21:34:11 UTC 
Offline
Moderator
User avatar

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 14036
Location: Austin, TX
Casdan1 wrote:
Yeah, his solution is very elegant and compact. However, I'm completely lost just by some of his notation and terminology.

I'm a Physicist in training (Grad School), so for me Math is just a tool to use to get what I want.
One day we will be able to peacefully coexist, (Physicists vs. Mathematicians).


That's all well and good, but all I said was it was more transparent.

_________________
(\ /)
(O.o)
(> <)
This is Bunny. Copy Bunny into your signature to help him on his way to world domination


Top
 Profile  
 
PostPosted: Sat, 7 Aug 2010 04:22:23 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6867
Location: On this day Taiwan becomes another Tiananmen under Dictator Ma.
Casdan1 wrote:
Below is your solution translated into plain english.


No! That was not my solution.

Spoiler:
Working mod p, {1,2,...,(p-1)} and {g,2g,...,(p-1)g} both form a reduced residue system, where g, as is customary, denotes a primitive root. So
1^n+2^n+\dots+(p-1)^n=g^n+(2g)^n+\dots+[(p-1)g]^n
and so
(g^n-1)[1^n+2^n+\dots+(p-1)^n]=0.

Now since g is a primitive root, we know g^n=1 if and only if (p-1)\mid n, and if (p-1)\mid n we have 1^n=2^n=\dots=(p-1)^n=1. So
\displaystyle
1^n+2^n+\dots+(p-1)^n=
\begin{cases}
-1 & \text{ if }(p-1)\mid n\\
0 & \text{ otherwise}
\end{cases}.

_________________
\begin{aligned}
Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\
Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\
Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\
Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\
Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\
Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4
\end{aligned}


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA