How to calculate mod of number with big exponent [duplicate]
$begingroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
8 answers
Mod of numbers with large exponents
3 answers
I want to find
$$
5^{133} mod 8.
$$
I have noticed that $5^n mod 8 = 5$ when $n$ is uneven and 1 otherwise, which would lead me to say that $5^{133} mod 8 = 5$ But I don't know how to prove this. How can I prove that this is the case (or find another solution if it is not)?
algebra-precalculus arithmetic
$endgroup$
marked as duplicate by Bill Dubuque
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
3 hours ago
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 |
$begingroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
8 answers
Mod of numbers with large exponents
3 answers
I want to find
$$
5^{133} mod 8.
$$
I have noticed that $5^n mod 8 = 5$ when $n$ is uneven and 1 otherwise, which would lead me to say that $5^{133} mod 8 = 5$ But I don't know how to prove this. How can I prove that this is the case (or find another solution if it is not)?
algebra-precalculus arithmetic
$endgroup$
marked as duplicate by Bill Dubuque
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
3 hours ago
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.
1
$begingroup$
Hint: $bmod 8!: color{#c00}{5^{large 2}equiv 1},Rightarrow, 5^{large 2n}equiv (color{#c00}{5^{large 2}})^{large n}equiv color{#c00}1^{large n}equiv 1 $
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
What does the triple equal sign mean?
$endgroup$
– Sandi
6 hours ago
$begingroup$
25 leaves a remainder of 1 when divided by 8 so it means they are "equivalent" under mod 8
$endgroup$
– Eleven-Eleven
6 hours ago
$begingroup$
@Sandi this is the common way to write congruences.
$endgroup$
– Mark
6 hours ago
add a comment |
$begingroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
8 answers
Mod of numbers with large exponents
3 answers
I want to find
$$
5^{133} mod 8.
$$
I have noticed that $5^n mod 8 = 5$ when $n$ is uneven and 1 otherwise, which would lead me to say that $5^{133} mod 8 = 5$ But I don't know how to prove this. How can I prove that this is the case (or find another solution if it is not)?
algebra-precalculus arithmetic
$endgroup$
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
8 answers
Mod of numbers with large exponents
3 answers
I want to find
$$
5^{133} mod 8.
$$
I have noticed that $5^n mod 8 = 5$ when $n$ is uneven and 1 otherwise, which would lead me to say that $5^{133} mod 8 = 5$ But I don't know how to prove this. How can I prove that this is the case (or find another solution if it is not)?
This question already has an answer here:
How do I compute $a^b,bmod c$ by hand?
8 answers
Mod of numbers with large exponents
3 answers
algebra-precalculus arithmetic
algebra-precalculus arithmetic
edited 6 hours ago
Sandi
asked 6 hours ago
SandiSandi
262112
262112
marked as duplicate by Bill Dubuque
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
3 hours ago
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 Bill Dubuque
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
3 hours ago
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.
1
$begingroup$
Hint: $bmod 8!: color{#c00}{5^{large 2}equiv 1},Rightarrow, 5^{large 2n}equiv (color{#c00}{5^{large 2}})^{large n}equiv color{#c00}1^{large n}equiv 1 $
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
What does the triple equal sign mean?
$endgroup$
– Sandi
6 hours ago
$begingroup$
25 leaves a remainder of 1 when divided by 8 so it means they are "equivalent" under mod 8
$endgroup$
– Eleven-Eleven
6 hours ago
$begingroup$
@Sandi this is the common way to write congruences.
$endgroup$
– Mark
6 hours ago
add a comment |
1
$begingroup$
Hint: $bmod 8!: color{#c00}{5^{large 2}equiv 1},Rightarrow, 5^{large 2n}equiv (color{#c00}{5^{large 2}})^{large n}equiv color{#c00}1^{large n}equiv 1 $
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
What does the triple equal sign mean?
$endgroup$
– Sandi
6 hours ago
$begingroup$
25 leaves a remainder of 1 when divided by 8 so it means they are "equivalent" under mod 8
$endgroup$
– Eleven-Eleven
6 hours ago
$begingroup$
@Sandi this is the common way to write congruences.
$endgroup$
– Mark
6 hours ago
1
1
$begingroup$
Hint: $bmod 8!: color{#c00}{5^{large 2}equiv 1},Rightarrow, 5^{large 2n}equiv (color{#c00}{5^{large 2}})^{large n}equiv color{#c00}1^{large n}equiv 1 $
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
Hint: $bmod 8!: color{#c00}{5^{large 2}equiv 1},Rightarrow, 5^{large 2n}equiv (color{#c00}{5^{large 2}})^{large n}equiv color{#c00}1^{large n}equiv 1 $
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
What does the triple equal sign mean?
$endgroup$
– Sandi
6 hours ago
$begingroup$
What does the triple equal sign mean?
$endgroup$
– Sandi
6 hours ago
$begingroup$
25 leaves a remainder of 1 when divided by 8 so it means they are "equivalent" under mod 8
$endgroup$
– Eleven-Eleven
6 hours ago
$begingroup$
25 leaves a remainder of 1 when divided by 8 so it means they are "equivalent" under mod 8
$endgroup$
– Eleven-Eleven
6 hours ago
$begingroup$
@Sandi this is the common way to write congruences.
$endgroup$
– Mark
6 hours ago
$begingroup$
@Sandi this is the common way to write congruences.
$endgroup$
– Mark
6 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
First of all it is easy to see that $5^2equiv 1$ (mod $8$). We also know that $133=66times 2+1$. Hence
$5^{133}equiv 5^{2times 66+1}equiv 5times (5^2)^{66}equiv 5times 1^{66}equiv 5$ (mod $8$).
$endgroup$
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
|
show 1 more comment
$begingroup$
"Highbrow method":
If you undertake to learn any number theory , there is Euler's theorem: $$a^{varphi (n)}cong1pmod n$$, for $a$ relatively prime to $n$.
($varphi$ is Euler's totient function, and just returns the number of positive integers less than $n$ that are relatively prime to $n$.)
Now $varphi (8)=4$. Hence $5^4cong1pmod8.$
Use this to reduce the exponent: $133=4×33+1implies5^{133}=(5^4)^{33}cdot 5cong5pmod8$.
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First of all it is easy to see that $5^2equiv 1$ (mod $8$). We also know that $133=66times 2+1$. Hence
$5^{133}equiv 5^{2times 66+1}equiv 5times (5^2)^{66}equiv 5times 1^{66}equiv 5$ (mod $8$).
$endgroup$
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
|
show 1 more comment
$begingroup$
First of all it is easy to see that $5^2equiv 1$ (mod $8$). We also know that $133=66times 2+1$. Hence
$5^{133}equiv 5^{2times 66+1}equiv 5times (5^2)^{66}equiv 5times 1^{66}equiv 5$ (mod $8$).
$endgroup$
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
|
show 1 more comment
$begingroup$
First of all it is easy to see that $5^2equiv 1$ (mod $8$). We also know that $133=66times 2+1$. Hence
$5^{133}equiv 5^{2times 66+1}equiv 5times (5^2)^{66}equiv 5times 1^{66}equiv 5$ (mod $8$).
$endgroup$
First of all it is easy to see that $5^2equiv 1$ (mod $8$). We also know that $133=66times 2+1$. Hence
$5^{133}equiv 5^{2times 66+1}equiv 5times (5^2)^{66}equiv 5times 1^{66}equiv 5$ (mod $8$).
edited 6 hours ago
J. W. Tanner
2,0591117
2,0591117
answered 6 hours ago
MarkMark
8,113420
8,113420
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
|
show 1 more comment
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
1
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
$begingroup$
Should the first triple-equal sign on the second row not be a normal equal sign? And the second one too?
$endgroup$
– Sandi
6 hours ago
1
1
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
Yes, you can also write regular equality there. But if two numbers are equal in $mathbb{Z}$ then they are also congruent mod $n$ for any $ninmathbb{N}$, and because we only care about congruence here I decided to write congruence from the beginning.
$endgroup$
– Mark
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
$begingroup$
I don't understand how you do the step $5 times (5^2)^{66} equiv 5 times 1^{66} (mathrm{mod} 8)$. Could you clarify please?
$endgroup$
– Sandi
6 hours ago
1
1
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
$5^2equiv 1$(mod $8$), hence $(5^2)^{66}equiv 1^{66}equiv 1$(mod $8$). That's it. It all follows from a basic theorem on modular arithmetic: that if $aequiv b$(mod $n$) and $cequiv d$(mod $n$) then $abequiv cd$(mod $n$). In other words multiplication mod $n$ is well defined. (same thing can we said about sum mod $n$)
$endgroup$
– Mark
6 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
$begingroup$
I found a similar thing in my book, but it said that $ac equiv bd (modn)$. Did you make a typo or is it a different theorem?
$endgroup$
– Sandi
5 hours ago
|
show 1 more comment
$begingroup$
"Highbrow method":
If you undertake to learn any number theory , there is Euler's theorem: $$a^{varphi (n)}cong1pmod n$$, for $a$ relatively prime to $n$.
($varphi$ is Euler's totient function, and just returns the number of positive integers less than $n$ that are relatively prime to $n$.)
Now $varphi (8)=4$. Hence $5^4cong1pmod8.$
Use this to reduce the exponent: $133=4×33+1implies5^{133}=(5^4)^{33}cdot 5cong5pmod8$.
$endgroup$
add a comment |
$begingroup$
"Highbrow method":
If you undertake to learn any number theory , there is Euler's theorem: $$a^{varphi (n)}cong1pmod n$$, for $a$ relatively prime to $n$.
($varphi$ is Euler's totient function, and just returns the number of positive integers less than $n$ that are relatively prime to $n$.)
Now $varphi (8)=4$. Hence $5^4cong1pmod8.$
Use this to reduce the exponent: $133=4×33+1implies5^{133}=(5^4)^{33}cdot 5cong5pmod8$.
$endgroup$
add a comment |
$begingroup$
"Highbrow method":
If you undertake to learn any number theory , there is Euler's theorem: $$a^{varphi (n)}cong1pmod n$$, for $a$ relatively prime to $n$.
($varphi$ is Euler's totient function, and just returns the number of positive integers less than $n$ that are relatively prime to $n$.)
Now $varphi (8)=4$. Hence $5^4cong1pmod8.$
Use this to reduce the exponent: $133=4×33+1implies5^{133}=(5^4)^{33}cdot 5cong5pmod8$.
$endgroup$
"Highbrow method":
If you undertake to learn any number theory , there is Euler's theorem: $$a^{varphi (n)}cong1pmod n$$, for $a$ relatively prime to $n$.
($varphi$ is Euler's totient function, and just returns the number of positive integers less than $n$ that are relatively prime to $n$.)
Now $varphi (8)=4$. Hence $5^4cong1pmod8.$
Use this to reduce the exponent: $133=4×33+1implies5^{133}=(5^4)^{33}cdot 5cong5pmod8$.
edited 5 hours ago
answered 5 hours ago
Chris CusterChris Custer
13.6k3827
13.6k3827
add a comment |
add a comment |
1
$begingroup$
Hint: $bmod 8!: color{#c00}{5^{large 2}equiv 1},Rightarrow, 5^{large 2n}equiv (color{#c00}{5^{large 2}})^{large n}equiv color{#c00}1^{large n}equiv 1 $
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
What does the triple equal sign mean?
$endgroup$
– Sandi
6 hours ago
$begingroup$
25 leaves a remainder of 1 when divided by 8 so it means they are "equivalent" under mod 8
$endgroup$
– Eleven-Eleven
6 hours ago
$begingroup$
@Sandi this is the common way to write congruences.
$endgroup$
– Mark
6 hours ago