How to calculate mod of number with big exponent [duplicate]












1












$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)?










share|cite|improve this question











$endgroup$



marked as duplicate by Bill Dubuque algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

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
















1












$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)?










share|cite|improve this question











$endgroup$



marked as duplicate by Bill Dubuque algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

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














1












1








1





$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)?










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 6 hours ago







Sandi

















asked 6 hours ago









SandiSandi

262112




262112




marked as duplicate by Bill Dubuque algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

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 algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

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














  • 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










2 Answers
2






active

oldest

votes


















6












$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$).






share|cite|improve this answer











$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



















0












$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$.






share|cite|improve this answer











$endgroup$




















    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    6












    $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$).






    share|cite|improve this answer











    $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
















    6












    $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$).






    share|cite|improve this answer











    $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














    6












    6








    6





    $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$).






    share|cite|improve this answer











    $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$).







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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


















    • $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











    0












    $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$.






    share|cite|improve this answer











    $endgroup$


















      0












      $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$.






      share|cite|improve this answer











      $endgroup$
















        0












        0








        0





        $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$.






        share|cite|improve this answer











        $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$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 5 hours ago

























        answered 5 hours ago









        Chris CusterChris Custer

        13.6k3827




        13.6k3827















            Popular posts from this blog

            Polycentropodidae

            Magento 2 Error message: Invalid state change requested

            Paulmy