Mixing
Find the remainder of $S = sum_i=0^99 (n+i)^6 + 2^2^2558 + 1$ divided by $100$.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
If $n$ is a positive integer, find the remainder of the following number divided by $100$:
$$S = sum_i=0^99 (n+i)^6 + 2^2^2558 + 1$$
I've wrote a program using logarithmic exponentiation and big integers to find that $2^2^2558 equiv 16 pmod100$. But I don't know what can I do with $sum_i=0^99 (n+i)^6$. Can you help me continue the problem, please? Thanks!
modular-arithmetic
asked Jul 18 at 18:51
Iulian Oleniuc
3619
add a comment |Â
up vote
1
down vote
favorite
If $n$ is a positive integer, find the remainder of the following number divided by $100$:
$$S = sum_i=0^99 (n+i)^6 + 2^2^2558 + 1$$
I've wrote a program using logarithmic exponentiation and big integers to find that $2^2^2558 equiv 16 pmod100$. But I don't know what can I do with $sum_i=0^99 (n+i)^6$. Can you help me continue the problem, please? Thanks!
modular-arithmetic
asked Jul 18 at 18:51
Iulian Oleniuc
3619
1
Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences?
– quid♦
Jul 18 at 18:57
Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^2^2558$ divided by $100$?
– Iulian Oleniuc
Jul 18 at 19:00
1
much more elegant. $2^20=1mod 25$. $2^4equiv 1mod 5$ so $2^2558equiv 2^2=4mod 5$. $2^2558equiv 0 mod 4$ so $2^2558equiv 16mod 20$. so $2^2^2558equiv 2^16=256*256equiv 36equiv 11mod 25$. And $2^2^2558equiv 0 mod 4$ so $2^2^2558equiv 36mod 100$. Unless I made an arithmetic error which is very likely.
– fleablood
Jul 18 at 19:35
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
If $n$ is a positive integer, find the remainder of the following number divided by $100$:
$$S = sum_i=0^99 (n+i)^6 + 2^2^2558 + 1$$
I've wrote a program using logarithmic exponentiation and big integers to find that $2^2^2558 equiv 16 pmod100$. But I don't know what can I do with $sum_i=0^99 (n+i)^6$. Can you help me continue the problem, please? Thanks!
modular-arithmetic
asked Jul 18 at 18:51
Iulian Oleniuc
3619
If $n$ is a positive integer, find the remainder of the following number divided by $100$:
$$S = sum_i=0^99 (n+i)^6 + 2^2^2558 + 1$$
I've wrote a program using logarithmic exponentiation and big integers to find that $2^2^2558 equiv 16 pmod100$. But I don't know what can I do with $sum_i=0^99 (n+i)^6$. Can you help me continue the problem, please? Thanks!
modular-arithmetic
asked Jul 18 at 18:51
Iulian Oleniuc
3619
asked Jul 18 at 18:51
Iulian Oleniuc
3619
asked Jul 18 at 18:51
Iulian Oleniuc
3619
asked Jul 18 at 18:51
Iulian Oleniuc
3619
3619
1
Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences?
– quid♦
Jul 18 at 18:57
Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^2^2558$ divided by $100$?
– Iulian Oleniuc
Jul 18 at 19:00
1
much more elegant. $2^20=1mod 25$. $2^4equiv 1mod 5$ so $2^2558equiv 2^2=4mod 5$. $2^2558equiv 0 mod 4$ so $2^2558equiv 16mod 20$. so $2^2^2558equiv 2^16=256*256equiv 36equiv 11mod 25$. And $2^2^2558equiv 0 mod 4$ so $2^2^2558equiv 36mod 100$. Unless I made an arithmetic error which is very likely.
– fleablood
Jul 18 at 19:35
add a comment |Â
1
Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences?
– quid♦
Jul 18 at 18:57
Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^2^2558$ divided by $100$?
– Iulian Oleniuc
Jul 18 at 19:00
1
much more elegant. $2^20=1mod 25$. $2^4equiv 1mod 5$ so $2^2558equiv 2^2=4mod 5$. $2^2558equiv 0 mod 4$ so $2^2558equiv 16mod 20$. so $2^2^2558equiv 2^16=256*256equiv 36equiv 11mod 25$. And $2^2^2558equiv 0 mod 4$ so $2^2^2558equiv 36mod 100$. Unless I made an arithmetic error which is very likely.
– fleablood
Jul 18 at 19:35
1
1
Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences?
– quid♦
Jul 18 at 18:57
Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences?
– quid♦
Jul 18 at 18:57
Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^2^2558$ divided by $100$?
– Iulian Oleniuc
Jul 18 at 19:00
Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^2^2558$ divided by $100$?
– Iulian Oleniuc
Jul 18 at 19:00
1
1
much more elegant. $2^20=1mod 25$. $2^4equiv 1mod 5$ so $2^2558equiv 2^2=4mod 5$. $2^2558equiv 0 mod 4$ so $2^2558equiv 16mod 20$. so $2^2^2558equiv 2^16=256*256equiv 36equiv 11mod 25$. And $2^2^2558equiv 0 mod 4$ so $2^2^2558equiv 36mod 100$. Unless I made an arithmetic error which is very likely.
– fleablood
Jul 18 at 19:35
much more elegant. $2^20=1mod 25$. $2^4equiv 1mod 5$ so $2^2558equiv 2^2=4mod 5$. $2^2558equiv 0 mod 4$ so $2^2558equiv 16mod 20$. so $2^2^2558equiv 2^16=256*256equiv 36equiv 11mod 25$. And $2^2^2558equiv 0 mod 4$ so $2^2^2558equiv 36mod 100$. Unless I made an arithmetic error which is very likely.
– fleablood
Jul 18 at 19:35
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
First note that $$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong 2quadtextmod 4$$ since$$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong1^6+2^6+3^6+4^6cong2qquad textmod 4$$since we have $25$ of such 4-tuple terms we can say that $$sum_i=0^99(n+i)^6cong 2quadtextmod 4$$also divisible by 25 since $$sum_i=0^24(n+i)^6congsum_i=0^24i^6=sum_i=1^24i^6textmod 25$$and since $$i^6cong(25-i)^6textmod 25$$ it suffices to show that $$sum_i=1^12i^6textmod 25$$or $$1^6+2^6+3^6+4^6+6^6+7^6+8^6+9^6+11^6+12^6cong 0textmod 25$$but this is true since $$25|1+7^6\25|3^6+4^6\25|2^6+11^6\25|6^6+8^6\25|9^6+12^6$$which completes our proof since $$sum_i=0^99(n+i)^6=sum_i=0^24(n+i)^6+sum_i=25^49(n+i)^6+sum_i=50^74(n+i)^6+sum_i=75^99(n+i)^6cong 0quadtextmod 25$$
From the other side, $2^2^2558$ is divisible by 4 and we have $$2^7cong3quadtextmod 25\2^21cong27cong 2quadtextmod 25\2^20cong1quadtextmod 25$$to find the remainder of division of $2^2^2558$ note that $$2^2cong -1quadtextmod 5$$here we obtain$$2^2556cong 1quadtextmod 5$$therefore $$2^2558cong 4quadtextmod 20$$finally by defining $2^2558=20u+4$ we conclude that $$2^2^2558=2^20u+4=16cdot (2^20)^ucong 16cong -9quadtextmod 25$$since $2^2^2558$ is also divisible by 4 we finally get$$2^2^2558=100k+16$$which means that $$Large Scong-33quadtextmod 100$$
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
add a comment |Â
up vote
1
down vote
If you know how to calculate the least universal exponent or Carmichael function $lambda$, you know that $lambda(100)=20$ and $lambda(20)=4$ and thus
$2^large 2^2558equiv 2^large (2^2558 bmod 20)equiv 2^large (2^2558 bmod 4 bmod 20)equiv 2^large (2^2bmod 20)equiv 2^4 equiv 16 bmod 100$
Note that the $(n+i)$ term will take on every residue value $bmod 100$ exactly once, no matter what the value of $n$ is. So there is only one answer, rather than a function based on $n$, and we can simply consider
$$Sequiv left (sum_i=0^99 i^6 + 16 + 1 right )bmod 100$$
By reviewing the expansion it's clear that $i^6equiv (50-i)^6equiv (50+i)^6 equiv (100-i)^6bmod 100$ . Then
$$Sequivleft( 4sum_i=1^24 i^6 + 2cdot 25^6 + 17 right )bmod 100$$
Clearly $25^kequiv 25 bmod 100$ for $k>0$. Now there's probably something smart to do with that remaining sum, but I can't see it it immediately. It's pretty clear to me from considering primitive roots that the sum of all sixth powers $bmod 100$ will be the same as the sum of all squares, but a little hard to prove briefly. Nevertheless I enlisted the help of a spreadsheet to show
$$sum_i=1^24 i^6 equiv 0 bmod 100$$
Thus
$$Sequivleft( 4cdot 0 + 2cdot 25 + 17 right ) equiv 67 bmod 100$$
answered Jul 18 at 19:52
Joffan
31.9k43169
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
First note that $$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong 2quadtextmod 4$$ since$$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong1^6+2^6+3^6+4^6cong2qquad textmod 4$$since we have $25$ of such 4-tuple terms we can say that $$sum_i=0^99(n+i)^6cong 2quadtextmod 4$$also divisible by 25 since $$sum_i=0^24(n+i)^6congsum_i=0^24i^6=sum_i=1^24i^6textmod 25$$and since $$i^6cong(25-i)^6textmod 25$$ it suffices to show that $$sum_i=1^12i^6textmod 25$$or $$1^6+2^6+3^6+4^6+6^6+7^6+8^6+9^6+11^6+12^6cong 0textmod 25$$but this is true since $$25|1+7^6\25|3^6+4^6\25|2^6+11^6\25|6^6+8^6\25|9^6+12^6$$which completes our proof since $$sum_i=0^99(n+i)^6=sum_i=0^24(n+i)^6+sum_i=25^49(n+i)^6+sum_i=50^74(n+i)^6+sum_i=75^99(n+i)^6cong 0quadtextmod 25$$
From the other side, $2^2^2558$ is divisible by 4 and we have $$2^7cong3quadtextmod 25\2^21cong27cong 2quadtextmod 25\2^20cong1quadtextmod 25$$to find the remainder of division of $2^2^2558$ note that $$2^2cong -1quadtextmod 5$$here we obtain$$2^2556cong 1quadtextmod 5$$therefore $$2^2558cong 4quadtextmod 20$$finally by defining $2^2558=20u+4$ we conclude that $$2^2^2558=2^20u+4=16cdot (2^20)^ucong 16cong -9quadtextmod 25$$since $2^2^2558$ is also divisible by 4 we finally get$$2^2^2558=100k+16$$which means that $$Large Scong-33quadtextmod 100$$
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
add a comment |Â
up vote
1
down vote
accepted
First note that $$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong 2quadtextmod 4$$ since$$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong1^6+2^6+3^6+4^6cong2qquad textmod 4$$since we have $25$ of such 4-tuple terms we can say that $$sum_i=0^99(n+i)^6cong 2quadtextmod 4$$also divisible by 25 since $$sum_i=0^24(n+i)^6congsum_i=0^24i^6=sum_i=1^24i^6textmod 25$$and since $$i^6cong(25-i)^6textmod 25$$ it suffices to show that $$sum_i=1^12i^6textmod 25$$or $$1^6+2^6+3^6+4^6+6^6+7^6+8^6+9^6+11^6+12^6cong 0textmod 25$$but this is true since $$25|1+7^6\25|3^6+4^6\25|2^6+11^6\25|6^6+8^6\25|9^6+12^6$$which completes our proof since $$sum_i=0^99(n+i)^6=sum_i=0^24(n+i)^6+sum_i=25^49(n+i)^6+sum_i=50^74(n+i)^6+sum_i=75^99(n+i)^6cong 0quadtextmod 25$$
From the other side, $2^2^2558$ is divisible by 4 and we have $$2^7cong3quadtextmod 25\2^21cong27cong 2quadtextmod 25\2^20cong1quadtextmod 25$$to find the remainder of division of $2^2^2558$ note that $$2^2cong -1quadtextmod 5$$here we obtain$$2^2556cong 1quadtextmod 5$$therefore $$2^2558cong 4quadtextmod 20$$finally by defining $2^2558=20u+4$ we conclude that $$2^2^2558=2^20u+4=16cdot (2^20)^ucong 16cong -9quadtextmod 25$$since $2^2^2558$ is also divisible by 4 we finally get$$2^2^2558=100k+16$$which means that $$Large Scong-33quadtextmod 100$$
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
First note that $$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong 2quadtextmod 4$$ since$$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong1^6+2^6+3^6+4^6cong2qquad textmod 4$$since we have $25$ of such 4-tuple terms we can say that $$sum_i=0^99(n+i)^6cong 2quadtextmod 4$$also divisible by 25 since $$sum_i=0^24(n+i)^6congsum_i=0^24i^6=sum_i=1^24i^6textmod 25$$and since $$i^6cong(25-i)^6textmod 25$$ it suffices to show that $$sum_i=1^12i^6textmod 25$$or $$1^6+2^6+3^6+4^6+6^6+7^6+8^6+9^6+11^6+12^6cong 0textmod 25$$but this is true since $$25|1+7^6\25|3^6+4^6\25|2^6+11^6\25|6^6+8^6\25|9^6+12^6$$which completes our proof since $$sum_i=0^99(n+i)^6=sum_i=0^24(n+i)^6+sum_i=25^49(n+i)^6+sum_i=50^74(n+i)^6+sum_i=75^99(n+i)^6cong 0quadtextmod 25$$
From the other side, $2^2^2558$ is divisible by 4 and we have $$2^7cong3quadtextmod 25\2^21cong27cong 2quadtextmod 25\2^20cong1quadtextmod 25$$to find the remainder of division of $2^2^2558$ note that $$2^2cong -1quadtextmod 5$$here we obtain$$2^2556cong 1quadtextmod 5$$therefore $$2^2558cong 4quadtextmod 20$$finally by defining $2^2558=20u+4$ we conclude that $$2^2^2558=2^20u+4=16cdot (2^20)^ucong 16cong -9quadtextmod 25$$since $2^2^2558$ is also divisible by 4 we finally get$$2^2^2558=100k+16$$which means that $$Large Scong-33quadtextmod 100$$
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
First note that $$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong 2quadtextmod 4$$ since$$k^6+(k+1)^6+(k+2)^6+(k+3)^6cong1^6+2^6+3^6+4^6cong2qquad textmod 4$$since we have $25$ of such 4-tuple terms we can say that $$sum_i=0^99(n+i)^6cong 2quadtextmod 4$$also divisible by 25 since $$sum_i=0^24(n+i)^6congsum_i=0^24i^6=sum_i=1^24i^6textmod 25$$and since $$i^6cong(25-i)^6textmod 25$$ it suffices to show that $$sum_i=1^12i^6textmod 25$$or $$1^6+2^6+3^6+4^6+6^6+7^6+8^6+9^6+11^6+12^6cong 0textmod 25$$but this is true since $$25|1+7^6\25|3^6+4^6\25|2^6+11^6\25|6^6+8^6\25|9^6+12^6$$which completes our proof since $$sum_i=0^99(n+i)^6=sum_i=0^24(n+i)^6+sum_i=25^49(n+i)^6+sum_i=50^74(n+i)^6+sum_i=75^99(n+i)^6cong 0quadtextmod 25$$
From the other side, $2^2^2558$ is divisible by 4 and we have $$2^7cong3quadtextmod 25\2^21cong27cong 2quadtextmod 25\2^20cong1quadtextmod 25$$to find the remainder of division of $2^2^2558$ note that $$2^2cong -1quadtextmod 5$$here we obtain$$2^2556cong 1quadtextmod 5$$therefore $$2^2558cong 4quadtextmod 20$$finally by defining $2^2558=20u+4$ we conclude that $$2^2^2558=2^20u+4=16cdot (2^20)^ucong 16cong -9quadtextmod 25$$since $2^2^2558$ is also divisible by 4 we finally get$$2^2^2558=100k+16$$which means that $$Large Scong-33quadtextmod 100$$
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
edited Jul 18 at 20:25
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
answered Jul 18 at 19:21
Mostafa Ayaz
8,6023630
8,6023630
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
add a comment |Â
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
It's easy to show that $sum_i=0^99(n+i)^6 equiv 50 pmod100$.
– Math Lover
Jul 18 at 19:28
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
Thank you @MathLover I fixed that.....
– Mostafa Ayaz
Jul 18 at 19:35
add a comment |Â
up vote
1
down vote
If you know how to calculate the least universal exponent or Carmichael function $lambda$, you know that $lambda(100)=20$ and $lambda(20)=4$ and thus
$2^large 2^2558equiv 2^large (2^2558 bmod 20)equiv 2^large (2^2558 bmod 4 bmod 20)equiv 2^large (2^2bmod 20)equiv 2^4 equiv 16 bmod 100$
Note that the $(n+i)$ term will take on every residue value $bmod 100$ exactly once, no matter what the value of $n$ is. So there is only one answer, rather than a function based on $n$, and we can simply consider
$$Sequiv left (sum_i=0^99 i^6 + 16 + 1 right )bmod 100$$
By reviewing the expansion it's clear that $i^6equiv (50-i)^6equiv (50+i)^6 equiv (100-i)^6bmod 100$ . Then
$$Sequivleft( 4sum_i=1^24 i^6 + 2cdot 25^6 + 17 right )bmod 100$$
Clearly $25^kequiv 25 bmod 100$ for $k>0$. Now there's probably something smart to do with that remaining sum, but I can't see it it immediately. It's pretty clear to me from considering primitive roots that the sum of all sixth powers $bmod 100$ will be the same as the sum of all squares, but a little hard to prove briefly. Nevertheless I enlisted the help of a spreadsheet to show
$$sum_i=1^24 i^6 equiv 0 bmod 100$$
Thus
$$Sequivleft( 4cdot 0 + 2cdot 25 + 17 right ) equiv 67 bmod 100$$
answered Jul 18 at 19:52
Joffan
31.9k43169
add a comment |Â
up vote
1
down vote
If you know how to calculate the least universal exponent or Carmichael function $lambda$, you know that $lambda(100)=20$ and $lambda(20)=4$ and thus
$2^large 2^2558equiv 2^large (2^2558 bmod 20)equiv 2^large (2^2558 bmod 4 bmod 20)equiv 2^large (2^2bmod 20)equiv 2^4 equiv 16 bmod 100$
Note that the $(n+i)$ term will take on every residue value $bmod 100$ exactly once, no matter what the value of $n$ is. So there is only one answer, rather than a function based on $n$, and we can simply consider
$$Sequiv left (sum_i=0^99 i^6 + 16 + 1 right )bmod 100$$
By reviewing the expansion it's clear that $i^6equiv (50-i)^6equiv (50+i)^6 equiv (100-i)^6bmod 100$ . Then
$$Sequivleft( 4sum_i=1^24 i^6 + 2cdot 25^6 + 17 right )bmod 100$$
Clearly $25^kequiv 25 bmod 100$ for $k>0$. Now there's probably something smart to do with that remaining sum, but I can't see it it immediately. It's pretty clear to me from considering primitive roots that the sum of all sixth powers $bmod 100$ will be the same as the sum of all squares, but a little hard to prove briefly. Nevertheless I enlisted the help of a spreadsheet to show
$$sum_i=1^24 i^6 equiv 0 bmod 100$$
Thus
$$Sequivleft( 4cdot 0 + 2cdot 25 + 17 right ) equiv 67 bmod 100$$
answered Jul 18 at 19:52
Joffan
31.9k43169
add a comment |Â
up vote
1
down vote
up vote
1
down vote
If you know how to calculate the least universal exponent or Carmichael function $lambda$, you know that $lambda(100)=20$ and $lambda(20)=4$ and thus
$2^large 2^2558equiv 2^large (2^2558 bmod 20)equiv 2^large (2^2558 bmod 4 bmod 20)equiv 2^large (2^2bmod 20)equiv 2^4 equiv 16 bmod 100$
Note that the $(n+i)$ term will take on every residue value $bmod 100$ exactly once, no matter what the value of $n$ is. So there is only one answer, rather than a function based on $n$, and we can simply consider
$$Sequiv left (sum_i=0^99 i^6 + 16 + 1 right )bmod 100$$
By reviewing the expansion it's clear that $i^6equiv (50-i)^6equiv (50+i)^6 equiv (100-i)^6bmod 100$ . Then
$$Sequivleft( 4sum_i=1^24 i^6 + 2cdot 25^6 + 17 right )bmod 100$$
Clearly $25^kequiv 25 bmod 100$ for $k>0$. Now there's probably something smart to do with that remaining sum, but I can't see it it immediately. It's pretty clear to me from considering primitive roots that the sum of all sixth powers $bmod 100$ will be the same as the sum of all squares, but a little hard to prove briefly. Nevertheless I enlisted the help of a spreadsheet to show
$$sum_i=1^24 i^6 equiv 0 bmod 100$$
Thus
$$Sequivleft( 4cdot 0 + 2cdot 25 + 17 right ) equiv 67 bmod 100$$
answered Jul 18 at 19:52
Joffan
31.9k43169
If you know how to calculate the least universal exponent or Carmichael function $lambda$, you know that $lambda(100)=20$ and $lambda(20)=4$ and thus
$2^large 2^2558equiv 2^large (2^2558 bmod 20)equiv 2^large (2^2558 bmod 4 bmod 20)equiv 2^large (2^2bmod 20)equiv 2^4 equiv 16 bmod 100$
Note that the $(n+i)$ term will take on every residue value $bmod 100$ exactly once, no matter what the value of $n$ is. So there is only one answer, rather than a function based on $n$, and we can simply consider
$$Sequiv left (sum_i=0^99 i^6 + 16 + 1 right )bmod 100$$
By reviewing the expansion it's clear that $i^6equiv (50-i)^6equiv (50+i)^6 equiv (100-i)^6bmod 100$ . Then
$$Sequivleft( 4sum_i=1^24 i^6 + 2cdot 25^6 + 17 right )bmod 100$$
Clearly $25^kequiv 25 bmod 100$ for $k>0$. Now there's probably something smart to do with that remaining sum, but I can't see it it immediately. It's pretty clear to me from considering primitive roots that the sum of all sixth powers $bmod 100$ will be the same as the sum of all squares, but a little hard to prove briefly. Nevertheless I enlisted the help of a spreadsheet to show
$$sum_i=1^24 i^6 equiv 0 bmod 100$$
Thus
$$Sequivleft( 4cdot 0 + 2cdot 25 + 17 right ) equiv 67 bmod 100$$
answered Jul 18 at 19:52
Joffan
31.9k43169
answered Jul 18 at 19:52
Joffan
31.9k43169
answered Jul 18 at 19:52
Joffan
31.9k43169
answered Jul 18 at 19:52
Joffan
31.9k43169
31.9k43169
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855883%2ffind-the-remainder-of-s-sum-i-099-ni6-222558-1-divided-b%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Note that the remainder of the sum on division by 100 is the same for all n. For the first, that's not the indetended approach. Do you know about congruences?
– quid♦
Jul 18 at 18:57
Yes, a little. Do you mean there's a more elegant way to find the remainder of $2^2^2558$ divided by $100$?
– Iulian Oleniuc
Jul 18 at 19:00
1
much more elegant. $2^20=1mod 25$. $2^4equiv 1mod 5$ so $2^2558equiv 2^2=4mod 5$. $2^2558equiv 0 mod 4$ so $2^2558equiv 16mod 20$. so $2^2^2558equiv 2^16=256*256equiv 36equiv 11mod 25$. And $2^2^2558equiv 0 mod 4$ so $2^2^2558equiv 36mod 100$. Unless I made an arithmetic error which is very likely.
– fleablood
Jul 18 at 19:35