Find the last four digits of $2^27653 - 1$ [duplicate]
Clash Royale CLAN TAG#URR8PPP
up vote
-2
down vote
favorite
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
7 answers
Find the last four digits of $2^ 27653 - 1. This is one of the questions in a mathematics contest.
I have tried to find the sequence but I found it impossible.
(I have used excel to do this and the sequence repeat after 2 ^ 15XX - 1)
elementary-number-theory
edited Aug 8 at 18:24
James
1,508318
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
marked as duplicate by Jyrki Lahtonen, Daniel Fischer♦ Aug 8 at 17:49
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
-2
down vote
favorite
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
7 answers
Find the last four digits of $2^ 27653 - 1. This is one of the questions in a mathematics contest.
I have tried to find the sequence but I found it impossible.
(I have used excel to do this and the sequence repeat after 2 ^ 15XX - 1)
elementary-number-theory
edited Aug 8 at 18:24
James
1,508318
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
marked as duplicate by Jyrki Lahtonen, Daniel Fischer♦ Aug 8 at 17:49
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
You should find the remainder modulo $5^4$. The remainder modulo $2^4$ should be easier :-). Use for example the techniques explained here for the first task. Then apply the Chinese Remainder Theorem. See other threads linked to that mother thread for VERY similar questions.
– Jyrki Lahtonen
Aug 8 at 17:17
add a comment |Â
up vote
-2
down vote
favorite
up vote
-2
down vote
favorite
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
7 answers
Find the last four digits of $2^ 27653 - 1. This is one of the questions in a mathematics contest.
I have tried to find the sequence but I found it impossible.
(I have used excel to do this and the sequence repeat after 2 ^ 15XX - 1)
elementary-number-theory
edited Aug 8 at 18:24
James
1,508318
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
7 answers
Find the last four digits of $2^ 27653 - 1. This is one of the questions in a mathematics contest.
I have tried to find the sequence but I found it impossible.
(I have used excel to do this and the sequence repeat after 2 ^ 15XX - 1)
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
7 answers
elementary-number-theory
edited Aug 8 at 18:24
James
1,508318
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
edited Aug 8 at 18:24
James
1,508318
edited Aug 8 at 18:24
James
1,508318
edited Aug 8 at 18:24
James
1,508318
1,508318
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
asked Aug 8 at 16:35
1C13 YEUNG SIN CHUN - 楊善進 1C13
31
31
marked as duplicate by Jyrki Lahtonen, Daniel Fischer♦ Aug 8 at 17:49
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Jyrki Lahtonen, Daniel Fischer♦ Aug 8 at 17:49
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
You should find the remainder modulo $5^4$. The remainder modulo $2^4$ should be easier :-). Use for example the techniques explained here for the first task. Then apply the Chinese Remainder Theorem. See other threads linked to that mother thread for VERY similar questions.
– Jyrki Lahtonen
Aug 8 at 17:17
add a comment |Â
You should find the remainder modulo $5^4$. The remainder modulo $2^4$ should be easier :-). Use for example the techniques explained here for the first task. Then apply the Chinese Remainder Theorem. See other threads linked to that mother thread for VERY similar questions.
– Jyrki Lahtonen
Aug 8 at 17:17
You should find the remainder modulo $5^4$. The remainder modulo $2^4$ should be easier :-). Use for example the techniques explained here for the first task. Then apply the Chinese Remainder Theorem. See other threads linked to that mother thread for VERY similar questions.
– Jyrki Lahtonen
Aug 8 at 17:17
You should find the remainder modulo $5^4$. The remainder modulo $2^4$ should be easier :-). Use for example the techniques explained here for the first task. Then apply the Chinese Remainder Theorem. See other threads linked to that mother thread for VERY similar questions.
– Jyrki Lahtonen
Aug 8 at 17:17
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
Using sage we get instantly
sage: R = Zmod(10000)
sage: R(2)^27653 - 1
2991
Using pari/gp also...
? Mod(2,10000)^27653 - 1
%11 = Mod(2991, 10000)
The human solution would be to compute the result modulo $2^4$ and modulo $5^4$. Of course, the number $$N=2^27653$$ is congruent to $0$ modulo $2^4$. Let us compute it modulo $5^4$. The Euler indicator of this number is $phi(5^4)=5^4left(1-frac 15right)=4cdot 5^3=500$. So
$$N=2^27653equiv 2^27653mod 500=2^153mod 5^4 .$$
Now we can compute $2^153$ explicitly, it is $11417981541647679048466287755595961091061972992$, or write it like $(2^51)^3$ and compute the third power of $(2^51mod 5^4)=(2251799813685248mod 5^4)=(5248mod 5^4)=(248mod 5^4)$. In each case we get the wanted $492$. Now we search among the numbers $492+5^4k$ with $0le k< 2^4$ the one which fulfills the condition modulo $2^4$. The number divisible by $16$ among them is $2992$. We get the same answer as a human...
answered Aug 8 at 18:40
dan_fulea
4,2371211
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
Using sage we get instantly
sage: R = Zmod(10000)
sage: R(2)^27653 - 1
2991
Using pari/gp also...
? Mod(2,10000)^27653 - 1
%11 = Mod(2991, 10000)
The human solution would be to compute the result modulo $2^4$ and modulo $5^4$. Of course, the number $$N=2^27653$$ is congruent to $0$ modulo $2^4$. Let us compute it modulo $5^4$. The Euler indicator of this number is $phi(5^4)=5^4left(1-frac 15right)=4cdot 5^3=500$. So
$$N=2^27653equiv 2^27653mod 500=2^153mod 5^4 .$$
Now we can compute $2^153$ explicitly, it is $11417981541647679048466287755595961091061972992$, or write it like $(2^51)^3$ and compute the third power of $(2^51mod 5^4)=(2251799813685248mod 5^4)=(5248mod 5^4)=(248mod 5^4)$. In each case we get the wanted $492$. Now we search among the numbers $492+5^4k$ with $0le k< 2^4$ the one which fulfills the condition modulo $2^4$. The number divisible by $16$ among them is $2992$. We get the same answer as a human...
answered Aug 8 at 18:40
dan_fulea
4,2371211
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
add a comment |Â
up vote
0
down vote
accepted
Using sage we get instantly
sage: R = Zmod(10000)
sage: R(2)^27653 - 1
2991
Using pari/gp also...
? Mod(2,10000)^27653 - 1
%11 = Mod(2991, 10000)
The human solution would be to compute the result modulo $2^4$ and modulo $5^4$. Of course, the number $$N=2^27653$$ is congruent to $0$ modulo $2^4$. Let us compute it modulo $5^4$. The Euler indicator of this number is $phi(5^4)=5^4left(1-frac 15right)=4cdot 5^3=500$. So
$$N=2^27653equiv 2^27653mod 500=2^153mod 5^4 .$$
Now we can compute $2^153$ explicitly, it is $11417981541647679048466287755595961091061972992$, or write it like $(2^51)^3$ and compute the third power of $(2^51mod 5^4)=(2251799813685248mod 5^4)=(5248mod 5^4)=(248mod 5^4)$. In each case we get the wanted $492$. Now we search among the numbers $492+5^4k$ with $0le k< 2^4$ the one which fulfills the condition modulo $2^4$. The number divisible by $16$ among them is $2992$. We get the same answer as a human...
answered Aug 8 at 18:40
dan_fulea
4,2371211
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
Using sage we get instantly
sage: R = Zmod(10000)
sage: R(2)^27653 - 1
2991
Using pari/gp also...
? Mod(2,10000)^27653 - 1
%11 = Mod(2991, 10000)
The human solution would be to compute the result modulo $2^4$ and modulo $5^4$. Of course, the number $$N=2^27653$$ is congruent to $0$ modulo $2^4$. Let us compute it modulo $5^4$. The Euler indicator of this number is $phi(5^4)=5^4left(1-frac 15right)=4cdot 5^3=500$. So
$$N=2^27653equiv 2^27653mod 500=2^153mod 5^4 .$$
Now we can compute $2^153$ explicitly, it is $11417981541647679048466287755595961091061972992$, or write it like $(2^51)^3$ and compute the third power of $(2^51mod 5^4)=(2251799813685248mod 5^4)=(5248mod 5^4)=(248mod 5^4)$. In each case we get the wanted $492$. Now we search among the numbers $492+5^4k$ with $0le k< 2^4$ the one which fulfills the condition modulo $2^4$. The number divisible by $16$ among them is $2992$. We get the same answer as a human...
answered Aug 8 at 18:40
dan_fulea
4,2371211
Using sage we get instantly
sage: R = Zmod(10000)
sage: R(2)^27653 - 1
2991
Using pari/gp also...
? Mod(2,10000)^27653 - 1
%11 = Mod(2991, 10000)
The human solution would be to compute the result modulo $2^4$ and modulo $5^4$. Of course, the number $$N=2^27653$$ is congruent to $0$ modulo $2^4$. Let us compute it modulo $5^4$. The Euler indicator of this number is $phi(5^4)=5^4left(1-frac 15right)=4cdot 5^3=500$. So
$$N=2^27653equiv 2^27653mod 500=2^153mod 5^4 .$$
Now we can compute $2^153$ explicitly, it is $11417981541647679048466287755595961091061972992$, or write it like $(2^51)^3$ and compute the third power of $(2^51mod 5^4)=(2251799813685248mod 5^4)=(5248mod 5^4)=(248mod 5^4)$. In each case we get the wanted $492$. Now we search among the numbers $492+5^4k$ with $0le k< 2^4$ the one which fulfills the condition modulo $2^4$. The number divisible by $16$ among them is $2992$. We get the same answer as a human...
answered Aug 8 at 18:40
dan_fulea
4,2371211
answered Aug 8 at 18:40
dan_fulea
4,2371211
answered Aug 8 at 18:40
dan_fulea
4,2371211
answered Aug 8 at 18:40
dan_fulea
4,2371211
4,2371211
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
add a comment |Â
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
Sorry, the answer was quickly typed, but the connection did not work, not it is submitted. Shall i remove it?!
– dan_fulea
Aug 8 at 18:41
add a comment |Â
You should find the remainder modulo $5^4$. The remainder modulo $2^4$ should be easier :-). Use for example the techniques explained here for the first task. Then apply the Chinese Remainder Theorem. See other threads linked to that mother thread for VERY similar questions.
– Jyrki Lahtonen
Aug 8 at 17:17