Prove that $3^{30} equiv 1 + 17 cdot 31 pmod{31^{2}}$.












2














I am reading "An introduction to algebraic systems" by Kazuo Matsuzaka.

There is the following problen without a solution in the book.

I guess this problem is easy, but I cannot solve it.




Prove that $3^{30} equiv 1 + 17 cdot 31 pmod{31^{2}}$




Of course, I can solve the above problem by direct calculation, but I wanna know smarter solution.



I did the following calculation for example, but I was not able to solve this problem.



By Fermat's little theorem,
$3^{30} equiv 1 + 17 cdot 31 pmod{31}.$



$1 + 17 cdot 31 equiv (1 + 31)^{17} equiv 32^{17} equiv 2^{85}pmod{31^2}$






elementary-number-theory modular-arithmetic problem-solving







share|cite|improve this question
























  • But.... that's it. What more do you need to do?
    – fleablood
    yesterday










  • @fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers.
    – Will R
    yesterday






  • 2




    @fleablood he has proven that $31$ divides $3^{30} - (1+ 17cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps)
    – stressed out
    yesterday


















2














I am reading "An introduction to algebraic systems" by Kazuo Matsuzaka.

There is the following problen without a solution in the book.

I guess this problem is easy, but I cannot solve it.




Prove that $3^{30} equiv 1 + 17 cdot 31 pmod{31^{2}}$




Of course, I can solve the above problem by direct calculation, but I wanna know smarter solution.



I did the following calculation for example, but I was not able to solve this problem.



By Fermat's little theorem,
$3^{30} equiv 1 + 17 cdot 31 pmod{31}.$



$1 + 17 cdot 31 equiv (1 + 31)^{17} equiv 32^{17} equiv 2^{85}pmod{31^2}$






elementary-number-theory modular-arithmetic problem-solving







share|cite|improve this question
























  • But.... that's it. What more do you need to do?
    – fleablood
    yesterday










  • @fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers.
    – Will R
    yesterday






  • 2




    @fleablood he has proven that $31$ divides $3^{30} - (1+ 17cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps)
    – stressed out
    yesterday
















2












2








2


1





I am reading "An introduction to algebraic systems" by Kazuo Matsuzaka.

There is the following problen without a solution in the book.

I guess this problem is easy, but I cannot solve it.




Prove that $3^{30} equiv 1 + 17 cdot 31 pmod{31^{2}}$




Of course, I can solve the above problem by direct calculation, but I wanna know smarter solution.



I did the following calculation for example, but I was not able to solve this problem.



By Fermat's little theorem,
$3^{30} equiv 1 + 17 cdot 31 pmod{31}.$



$1 + 17 cdot 31 equiv (1 + 31)^{17} equiv 32^{17} equiv 2^{85}pmod{31^2}$






elementary-number-theory modular-arithmetic problem-solving







share|cite|improve this question















I am reading "An introduction to algebraic systems" by Kazuo Matsuzaka.

There is the following problen without a solution in the book.

I guess this problem is easy, but I cannot solve it.




Prove that $3^{30} equiv 1 + 17 cdot 31 pmod{31^{2}}$




Of course, I can solve the above problem by direct calculation, but I wanna know smarter solution.



I did the following calculation for example, but I was not able to solve this problem.



By Fermat's little theorem,
$3^{30} equiv 1 + 17 cdot 31 pmod{31}.$



$1 + 17 cdot 31 equiv (1 + 31)^{17} equiv 32^{17} equiv 2^{85}pmod{31^2}$






elementary-number-theory modular-arithmetic problem-solving




elementary-number-theory modular-arithmetic problem-solving






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited yesterday

























asked yesterday









tchappy ha

435310




435310












  • But.... that's it. What more do you need to do?
    – fleablood
    yesterday










  • @fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers.
    – Will R
    yesterday






  • 2




    @fleablood he has proven that $31$ divides $3^{30} - (1+ 17cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps)
    – stressed out
    yesterday




















  • But.... that's it. What more do you need to do?
    – fleablood
    yesterday










  • @fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers.
    – Will R
    yesterday






  • 2




    @fleablood he has proven that $31$ divides $3^{30} - (1+ 17cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps)
    – stressed out
    yesterday


















But.... that's it. What more do you need to do?
– fleablood
yesterday




But.... that's it. What more do you need to do?
– fleablood
yesterday












@fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers.
– Will R
yesterday




@fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers.
– Will R
yesterday




2




2




@fleablood he has proven that $31$ divides $3^{30} - (1+ 17cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps)
– stressed out
yesterday






@fleablood he has proven that $31$ divides $3^{30} - (1+ 17cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps)
– stressed out
yesterday












1 Answer
1






active

oldest

votes


















4














Since $31$ is prime, by Fermat's Little Theorem, $3^{30}equiv 1 pmod{31}$. Thus, $3^{30}-1$ is a multiple of $31$. Now, let's consider $frac{3^{30}-1}{31} pmod{31}$:



$$frac{3^{30}-1}{31}=(3^{15}-1)frac{3^{15}+1}{31}=(3^{15}-1)(3^5+1)frac{1-3^5+3^{10}}{31}$$



Now, this requires some computation, but $3^5=243=8cdot 31-5$ (In particular, $3^5 equiv -5 pmod {31}$). Therefore:



$$frac{1-3^5+3^{10}}{31}=frac{1+5-8cdot 31+(8cdot 31-5)^2}{31}=frac{1+5-8cdot 31+25-80cdot 31+64cdot 31^2}{31} \ =1-8-80+64cdot 31=-87+64cdot 31 \ implies frac{1-3^5+3^{10}}{31}equiv -87equiv-3cdot 31+6equiv 6pmod{31}$$



Then, since $3^5equiv -5pmod{31}$, we have:
$$3^5+1equiv -4pmod{31}$$
$$3^{15}-1=(3^5)^3-1=(-5)^3-1=-125-1=-126=-4cdot 31-2equiv -2pmod{31}$$
Thus:
$$frac{3^{30}-1}{31}equiv -2cdot -4cdot 6equiv48equiv 17pmod{31}$$



In other words:
$$frac{3^{30}-1}{31}=17+31k text{ for some integer } k$$



Multiply both sides by $31$ and then add $1$:
$$3^{30}=1+17cdot 31+31^2k text{ for some integer } k$$



This can be converted into a statement with $pmod{31^2}$:
$$3^{30}equiv 1+17cdot 31pmod{31^2}$$






share|cite|improve this answer





















    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062383%2fprove-that-330-equiv-1-17-cdot-31-pmod312%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    4














    Since $31$ is prime, by Fermat's Little Theorem, $3^{30}equiv 1 pmod{31}$. Thus, $3^{30}-1$ is a multiple of $31$. Now, let's consider $frac{3^{30}-1}{31} pmod{31}$:



    $$frac{3^{30}-1}{31}=(3^{15}-1)frac{3^{15}+1}{31}=(3^{15}-1)(3^5+1)frac{1-3^5+3^{10}}{31}$$



    Now, this requires some computation, but $3^5=243=8cdot 31-5$ (In particular, $3^5 equiv -5 pmod {31}$). Therefore:



    $$frac{1-3^5+3^{10}}{31}=frac{1+5-8cdot 31+(8cdot 31-5)^2}{31}=frac{1+5-8cdot 31+25-80cdot 31+64cdot 31^2}{31} \ =1-8-80+64cdot 31=-87+64cdot 31 \ implies frac{1-3^5+3^{10}}{31}equiv -87equiv-3cdot 31+6equiv 6pmod{31}$$



    Then, since $3^5equiv -5pmod{31}$, we have:
    $$3^5+1equiv -4pmod{31}$$
    $$3^{15}-1=(3^5)^3-1=(-5)^3-1=-125-1=-126=-4cdot 31-2equiv -2pmod{31}$$
    Thus:
    $$frac{3^{30}-1}{31}equiv -2cdot -4cdot 6equiv48equiv 17pmod{31}$$



    In other words:
    $$frac{3^{30}-1}{31}=17+31k text{ for some integer } k$$



    Multiply both sides by $31$ and then add $1$:
    $$3^{30}=1+17cdot 31+31^2k text{ for some integer } k$$



    This can be converted into a statement with $pmod{31^2}$:
    $$3^{30}equiv 1+17cdot 31pmod{31^2}$$






    share|cite|improve this answer


























      4














      Since $31$ is prime, by Fermat's Little Theorem, $3^{30}equiv 1 pmod{31}$. Thus, $3^{30}-1$ is a multiple of $31$. Now, let's consider $frac{3^{30}-1}{31} pmod{31}$:



      $$frac{3^{30}-1}{31}=(3^{15}-1)frac{3^{15}+1}{31}=(3^{15}-1)(3^5+1)frac{1-3^5+3^{10}}{31}$$



      Now, this requires some computation, but $3^5=243=8cdot 31-5$ (In particular, $3^5 equiv -5 pmod {31}$). Therefore:



      $$frac{1-3^5+3^{10}}{31}=frac{1+5-8cdot 31+(8cdot 31-5)^2}{31}=frac{1+5-8cdot 31+25-80cdot 31+64cdot 31^2}{31} \ =1-8-80+64cdot 31=-87+64cdot 31 \ implies frac{1-3^5+3^{10}}{31}equiv -87equiv-3cdot 31+6equiv 6pmod{31}$$



      Then, since $3^5equiv -5pmod{31}$, we have:
      $$3^5+1equiv -4pmod{31}$$
      $$3^{15}-1=(3^5)^3-1=(-5)^3-1=-125-1=-126=-4cdot 31-2equiv -2pmod{31}$$
      Thus:
      $$frac{3^{30}-1}{31}equiv -2cdot -4cdot 6equiv48equiv 17pmod{31}$$



      In other words:
      $$frac{3^{30}-1}{31}=17+31k text{ for some integer } k$$



      Multiply both sides by $31$ and then add $1$:
      $$3^{30}=1+17cdot 31+31^2k text{ for some integer } k$$



      This can be converted into a statement with $pmod{31^2}$:
      $$3^{30}equiv 1+17cdot 31pmod{31^2}$$






      share|cite|improve this answer
























        4












        4








        4






        Since $31$ is prime, by Fermat's Little Theorem, $3^{30}equiv 1 pmod{31}$. Thus, $3^{30}-1$ is a multiple of $31$. Now, let's consider $frac{3^{30}-1}{31} pmod{31}$:



        $$frac{3^{30}-1}{31}=(3^{15}-1)frac{3^{15}+1}{31}=(3^{15}-1)(3^5+1)frac{1-3^5+3^{10}}{31}$$



        Now, this requires some computation, but $3^5=243=8cdot 31-5$ (In particular, $3^5 equiv -5 pmod {31}$). Therefore:



        $$frac{1-3^5+3^{10}}{31}=frac{1+5-8cdot 31+(8cdot 31-5)^2}{31}=frac{1+5-8cdot 31+25-80cdot 31+64cdot 31^2}{31} \ =1-8-80+64cdot 31=-87+64cdot 31 \ implies frac{1-3^5+3^{10}}{31}equiv -87equiv-3cdot 31+6equiv 6pmod{31}$$



        Then, since $3^5equiv -5pmod{31}$, we have:
        $$3^5+1equiv -4pmod{31}$$
        $$3^{15}-1=(3^5)^3-1=(-5)^3-1=-125-1=-126=-4cdot 31-2equiv -2pmod{31}$$
        Thus:
        $$frac{3^{30}-1}{31}equiv -2cdot -4cdot 6equiv48equiv 17pmod{31}$$



        In other words:
        $$frac{3^{30}-1}{31}=17+31k text{ for some integer } k$$



        Multiply both sides by $31$ and then add $1$:
        $$3^{30}=1+17cdot 31+31^2k text{ for some integer } k$$



        This can be converted into a statement with $pmod{31^2}$:
        $$3^{30}equiv 1+17cdot 31pmod{31^2}$$






        share|cite|improve this answer












        Since $31$ is prime, by Fermat's Little Theorem, $3^{30}equiv 1 pmod{31}$. Thus, $3^{30}-1$ is a multiple of $31$. Now, let's consider $frac{3^{30}-1}{31} pmod{31}$:



        $$frac{3^{30}-1}{31}=(3^{15}-1)frac{3^{15}+1}{31}=(3^{15}-1)(3^5+1)frac{1-3^5+3^{10}}{31}$$



        Now, this requires some computation, but $3^5=243=8cdot 31-5$ (In particular, $3^5 equiv -5 pmod {31}$). Therefore:



        $$frac{1-3^5+3^{10}}{31}=frac{1+5-8cdot 31+(8cdot 31-5)^2}{31}=frac{1+5-8cdot 31+25-80cdot 31+64cdot 31^2}{31} \ =1-8-80+64cdot 31=-87+64cdot 31 \ implies frac{1-3^5+3^{10}}{31}equiv -87equiv-3cdot 31+6equiv 6pmod{31}$$



        Then, since $3^5equiv -5pmod{31}$, we have:
        $$3^5+1equiv -4pmod{31}$$
        $$3^{15}-1=(3^5)^3-1=(-5)^3-1=-125-1=-126=-4cdot 31-2equiv -2pmod{31}$$
        Thus:
        $$frac{3^{30}-1}{31}equiv -2cdot -4cdot 6equiv48equiv 17pmod{31}$$



        In other words:
        $$frac{3^{30}-1}{31}=17+31k text{ for some integer } k$$



        Multiply both sides by $31$ and then add $1$:
        $$3^{30}=1+17cdot 31+31^2k text{ for some integer } k$$



        This can be converted into a statement with $pmod{31^2}$:
        $$3^{30}equiv 1+17cdot 31pmod{31^2}$$







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered yesterday









        Noble Mushtak

        15.1k1735




        15.1k1735






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062383%2fprove-that-330-equiv-1-17-cdot-31-pmod312%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            -

            Popular posts from this blog

            Mario Kart Wii

            Image
            Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! Mario Kart Wii From The Cutting Room Floor Jump to: navigation, search Mario Kart Wii Developer : Nintendo Publisher : Nintendo Platform : Wii Released in JP : April 10, 2008 Released in US : April 27, 2008 Released in EU : April 11, 2008 Released in AU : April 24, 2008 Released in KR : April 30, 2009 This game has unused animations. This game has unused areas. This game has unused code. This game has unused objects. This game has unused modes / minigames. This game has unused graphics. This game has unused models. This game has unused items. This game has unused music. This game has regional differences. This game has a notes page This game has a prerelease article Mario Kart Wii is the sixth game in the series (not counting Arcade editions), which intro...
            Read more

            Partial Derivative Guidance.

            Image
            0 $begingroup$ I was given this tricky problem in which I'm confuse on how to solve it and I would like some help: Let $v(x,y)$ be continuously differentiable function. Let the function $u(s,t)$ be given by $u(s,t) = sin(s)*v(s-2t,t^2)$ . Compute $du/ds$ and $du/dt$ in terms of $v$ and it's partial derivatives. My attempt (which is wrong): Using chain rule: $du/ds=(du/dx)(dx/ds) + (du/dy)(dy/ds)$ $du/dt=(du/dx)(dx/dt) + (du/dx)(dy/dt)$ So, $du/ds = sin(s)*v(x,y)*s + sin(s)*v(x,y)*0$ $du/dt = 2t*sin(s)*v(x,y) - 2*sin(s)*v(x,y)$ Thanks, calculus multivariable-calculus share | cite | improve this question edited Jan 19 at 19:38...
            Read more

            Understanding the size os this class of aleatory events

            Image
            0 1 $begingroup$ Hi I am having problems to understand this: I have: $Omega = [0,1]$ , $Lambda =$ all subsets with defined length Let $A_{0}$ = {A $subset$ [0,1]: A is finite union of intervals} 1º: My doubt is that $A_{0}$ is a algebra but its not a sigma algebra. Why? Also, A = $(0,1/2) cup (1/2,3/4) cup (3/4,7/8) cup ... cup(1-1/2^{n},1-1/2^{n+1})...$ 2º: So the class of aleatory events would be bigger than $A_{0}$ . Why? How the set A is greater than $A_{0}$ ? measure-theory share | cite | improve this question asked Jan 8 at 19:17 Diogo Bastos Diogo Bastos 116 6 ...
            Read more