Mixing
How to justify that the sequence $n^nbmod 5$ is periodic?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I'm asked in an exercise to give the possible reminders of $n^n bmod 5$ in a congruency that is a good fit for n.
After doing so calculations I note that there seems to be a cycle of reminders each $20$ numbers.
This is also supported by the fact that the reminder is related with $r5(n)$ but also with $r4(n)$ (the way I calculate the reminder, for $n$ that are coprime with $5$, is $r5( r5(n)^r4(n) )$ where $rX$ is the remainder modulo X).
I'm confident that the answer is related with the cycle of reminders from $n = 0$ to $n = 20$. All the reminders will repeat for $n geq 20$. But I'm not sure what would be a good justification of this. I guess the fact that $4 | 20$ and $5 | 20$, it's the least common multiple, has something to do with this.
modular-arithmetic
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
asked Jul 24 at 2:33
hhaamm
493
add a comment |Â
up vote
1
down vote
favorite
I'm asked in an exercise to give the possible reminders of $n^n bmod 5$ in a congruency that is a good fit for n.
After doing so calculations I note that there seems to be a cycle of reminders each $20$ numbers.
This is also supported by the fact that the reminder is related with $r5(n)$ but also with $r4(n)$ (the way I calculate the reminder, for $n$ that are coprime with $5$, is $r5( r5(n)^r4(n) )$ where $rX$ is the remainder modulo X).
I'm confident that the answer is related with the cycle of reminders from $n = 0$ to $n = 20$. All the reminders will repeat for $n geq 20$. But I'm not sure what would be a good justification of this. I guess the fact that $4 | 20$ and $5 | 20$, it's the least common multiple, has something to do with this.
modular-arithmetic
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
asked Jul 24 at 2:33
hhaamm
493
1
You can use Fermat's little theorem to compute the remainder of $(n+20)^n+20=n^n+20+text a multiple of 5$. And then the remainder of $n^n+20=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^n+20$ ends up with the same remainder as $n^n$.
– user578878
Jul 24 at 2:44
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm asked in an exercise to give the possible reminders of $n^n bmod 5$ in a congruency that is a good fit for n.
After doing so calculations I note that there seems to be a cycle of reminders each $20$ numbers.
This is also supported by the fact that the reminder is related with $r5(n)$ but also with $r4(n)$ (the way I calculate the reminder, for $n$ that are coprime with $5$, is $r5( r5(n)^r4(n) )$ where $rX$ is the remainder modulo X).
I'm confident that the answer is related with the cycle of reminders from $n = 0$ to $n = 20$. All the reminders will repeat for $n geq 20$. But I'm not sure what would be a good justification of this. I guess the fact that $4 | 20$ and $5 | 20$, it's the least common multiple, has something to do with this.
modular-arithmetic
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
asked Jul 24 at 2:33
hhaamm
493
I'm asked in an exercise to give the possible reminders of $n^n bmod 5$ in a congruency that is a good fit for n.
After doing so calculations I note that there seems to be a cycle of reminders each $20$ numbers.
This is also supported by the fact that the reminder is related with $r5(n)$ but also with $r4(n)$ (the way I calculate the reminder, for $n$ that are coprime with $5$, is $r5( r5(n)^r4(n) )$ where $rX$ is the remainder modulo X).
I'm confident that the answer is related with the cycle of reminders from $n = 0$ to $n = 20$. All the reminders will repeat for $n geq 20$. But I'm not sure what would be a good justification of this. I guess the fact that $4 | 20$ and $5 | 20$, it's the least common multiple, has something to do with this.
modular-arithmetic
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
asked Jul 24 at 2:33
hhaamm
493
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
edited Jul 24 at 10:26
Arnaud Mortier
18.9k22159
18.9k22159
asked Jul 24 at 2:33
hhaamm
493
asked Jul 24 at 2:33
hhaamm
493
asked Jul 24 at 2:33
hhaamm
493
493
1
You can use Fermat's little theorem to compute the remainder of $(n+20)^n+20=n^n+20+text a multiple of 5$. And then the remainder of $n^n+20=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^n+20$ ends up with the same remainder as $n^n$.
– user578878
Jul 24 at 2:44
add a comment |Â
1
You can use Fermat's little theorem to compute the remainder of $(n+20)^n+20=n^n+20+text a multiple of 5$. And then the remainder of $n^n+20=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^n+20$ ends up with the same remainder as $n^n$.
– user578878
Jul 24 at 2:44
1
1
You can use Fermat's little theorem to compute the remainder of $(n+20)^n+20=n^n+20+text a multiple of 5$. And then the remainder of $n^n+20=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^n+20$ ends up with the same remainder as $n^n$.
– user578878
Jul 24 at 2:44
You can use Fermat's little theorem to compute the remainder of $(n+20)^n+20=n^n+20+text a multiple of 5$. And then the remainder of $n^n+20=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^n+20$ ends up with the same remainder as $n^n$.
– user578878
Jul 24 at 2:44
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
You're right about $20$ being the least common multiple of $4$ and $5$ being relevant. Using Fermat's Little Theorem, we have
$$a^5 equiv a mathbfmod 5,$$
for all $a$. So, if $n > 1$, we have
beginalign*
(n + 20)^n + 20 &equiv (n + 20)^n-1 (n + 20)^21 \
&equiv (n + 20)^n-1 (n + 20) \
&equiv (n + 20)^n \
&equiv n^n.
endalign*
On the other hand, if $n = 1$, then
$$21^21 equiv 1^21 equiv 1.$$
In any case, we get what we want.
answered Jul 24 at 2:43
Theo Bendit
12k1843
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
add a comment |Â
up vote
1
down vote
Note that your expression $r5(n)^r4(n)$ only depends on $nbmod 5$ and $nbmod 4$. The pair of values of these repeat every $20$ as shown in the Chinese Remainder Theorem.
answered Jul 24 at 2:43
Ross Millikan
275k21186351
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
You're right about $20$ being the least common multiple of $4$ and $5$ being relevant. Using Fermat's Little Theorem, we have
$$a^5 equiv a mathbfmod 5,$$
for all $a$. So, if $n > 1$, we have
beginalign*
(n + 20)^n + 20 &equiv (n + 20)^n-1 (n + 20)^21 \
&equiv (n + 20)^n-1 (n + 20) \
&equiv (n + 20)^n \
&equiv n^n.
endalign*
On the other hand, if $n = 1$, then
$$21^21 equiv 1^21 equiv 1.$$
In any case, we get what we want.
answered Jul 24 at 2:43
Theo Bendit
12k1843
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
add a comment |Â
up vote
1
down vote
accepted
You're right about $20$ being the least common multiple of $4$ and $5$ being relevant. Using Fermat's Little Theorem, we have
$$a^5 equiv a mathbfmod 5,$$
for all $a$. So, if $n > 1$, we have
beginalign*
(n + 20)^n + 20 &equiv (n + 20)^n-1 (n + 20)^21 \
&equiv (n + 20)^n-1 (n + 20) \
&equiv (n + 20)^n \
&equiv n^n.
endalign*
On the other hand, if $n = 1$, then
$$21^21 equiv 1^21 equiv 1.$$
In any case, we get what we want.
answered Jul 24 at 2:43
Theo Bendit
12k1843
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You're right about $20$ being the least common multiple of $4$ and $5$ being relevant. Using Fermat's Little Theorem, we have
$$a^5 equiv a mathbfmod 5,$$
for all $a$. So, if $n > 1$, we have
beginalign*
(n + 20)^n + 20 &equiv (n + 20)^n-1 (n + 20)^21 \
&equiv (n + 20)^n-1 (n + 20) \
&equiv (n + 20)^n \
&equiv n^n.
endalign*
On the other hand, if $n = 1$, then
$$21^21 equiv 1^21 equiv 1.$$
In any case, we get what we want.
answered Jul 24 at 2:43
Theo Bendit
12k1843
You're right about $20$ being the least common multiple of $4$ and $5$ being relevant. Using Fermat's Little Theorem, we have
$$a^5 equiv a mathbfmod 5,$$
for all $a$. So, if $n > 1$, we have
beginalign*
(n + 20)^n + 20 &equiv (n + 20)^n-1 (n + 20)^21 \
&equiv (n + 20)^n-1 (n + 20) \
&equiv (n + 20)^n \
&equiv n^n.
endalign*
On the other hand, if $n = 1$, then
$$21^21 equiv 1^21 equiv 1.$$
In any case, we get what we want.
answered Jul 24 at 2:43
Theo Bendit
12k1843
answered Jul 24 at 2:43
Theo Bendit
12k1843
answered Jul 24 at 2:43
Theo Bendit
12k1843
answered Jul 24 at 2:43
Theo Bendit
12k1843
12k1843
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
add a comment |Â
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
"On the other hand, if $n=1$, then ..." What do you mean by this? I mean, what is this supposed to add to the answer?
– Arnaud Mortier
Jul 24 at 10:22
add a comment |Â
up vote
1
down vote
Note that your expression $r5(n)^r4(n)$ only depends on $nbmod 5$ and $nbmod 4$. The pair of values of these repeat every $20$ as shown in the Chinese Remainder Theorem.
answered Jul 24 at 2:43
Ross Millikan
275k21186351
add a comment |Â
up vote
1
down vote
Note that your expression $r5(n)^r4(n)$ only depends on $nbmod 5$ and $nbmod 4$. The pair of values of these repeat every $20$ as shown in the Chinese Remainder Theorem.
answered Jul 24 at 2:43
Ross Millikan
275k21186351
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Note that your expression $r5(n)^r4(n)$ only depends on $nbmod 5$ and $nbmod 4$. The pair of values of these repeat every $20$ as shown in the Chinese Remainder Theorem.
answered Jul 24 at 2:43
Ross Millikan
275k21186351
Note that your expression $r5(n)^r4(n)$ only depends on $nbmod 5$ and $nbmod 4$. The pair of values of these repeat every $20$ as shown in the Chinese Remainder Theorem.
answered Jul 24 at 2:43
Ross Millikan
275k21186351
answered Jul 24 at 2:43
Ross Millikan
275k21186351
answered Jul 24 at 2:43
Ross Millikan
275k21186351
answered Jul 24 at 2:43
Ross Millikan
275k21186351
275k21186351
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%2f2860953%2fhow-to-justify-that-the-sequence-nn-bmod-5-is-periodic%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
You can use Fermat's little theorem to compute the remainder of $(n+20)^n+20=n^n+20+text a multiple of 5$. And then the remainder of $n^n+20=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^n+20$ ends up with the same remainder as $n^n$.
– user578878
Jul 24 at 2:44