Use Euler's theorem to find the inverse of 17 modulo 31 in the range {1,…,30}.












0














This is a question from the MIT opencourseware Mathematics for Computer Science, problem set 3:



Use Euler's theorem to find the inverse of $17$ modulo $31$ in the range ${1,...,30}$.



I don't seem to be able to actually use Euler's theorem here. Since both $17$ and $31$ are primes the $gcd$ is $1$, so $K^{varphi(n)-1} = 17^{29}$, which works here for an inverse, but how does that help me find an inverse in the $1,...,30$ range?






modular-arithmetic







share|cite|improve this question
























  • It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $,17^{29},$ via exponentiation by repeated squaring and then notice right at the start that $,17^2equiv -1,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $,17^{-1}equiv -17equiv 12.,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise.
    – Bill Dubuque
    May 31 '15 at 22:18












  • The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm.
    – aristotle85
    May 31 '15 at 22:24








  • 1




    What results are discussed immediately before this?
    – Bill Dubuque
    May 31 '15 at 22:25
















0














This is a question from the MIT opencourseware Mathematics for Computer Science, problem set 3:



Use Euler's theorem to find the inverse of $17$ modulo $31$ in the range ${1,...,30}$.



I don't seem to be able to actually use Euler's theorem here. Since both $17$ and $31$ are primes the $gcd$ is $1$, so $K^{varphi(n)-1} = 17^{29}$, which works here for an inverse, but how does that help me find an inverse in the $1,...,30$ range?






modular-arithmetic







share|cite|improve this question
























  • It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $,17^{29},$ via exponentiation by repeated squaring and then notice right at the start that $,17^2equiv -1,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $,17^{-1}equiv -17equiv 12.,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise.
    – Bill Dubuque
    May 31 '15 at 22:18












  • The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm.
    – aristotle85
    May 31 '15 at 22:24








  • 1




    What results are discussed immediately before this?
    – Bill Dubuque
    May 31 '15 at 22:25














0












0








0







This is a question from the MIT opencourseware Mathematics for Computer Science, problem set 3:



Use Euler's theorem to find the inverse of $17$ modulo $31$ in the range ${1,...,30}$.



I don't seem to be able to actually use Euler's theorem here. Since both $17$ and $31$ are primes the $gcd$ is $1$, so $K^{varphi(n)-1} = 17^{29}$, which works here for an inverse, but how does that help me find an inverse in the $1,...,30$ range?






modular-arithmetic







share|cite|improve this question















This is a question from the MIT opencourseware Mathematics for Computer Science, problem set 3:



Use Euler's theorem to find the inverse of $17$ modulo $31$ in the range ${1,...,30}$.



I don't seem to be able to actually use Euler's theorem here. Since both $17$ and $31$ are primes the $gcd$ is $1$, so $K^{varphi(n)-1} = 17^{29}$, which works here for an inverse, but how does that help me find an inverse in the $1,...,30$ range?






modular-arithmetic




modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited May 31 '15 at 22:15









Alex M.

28k103058




28k103058










asked May 31 '15 at 22:06









aristotle85

6018




6018












  • It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $,17^{29},$ via exponentiation by repeated squaring and then notice right at the start that $,17^2equiv -1,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $,17^{-1}equiv -17equiv 12.,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise.
    – Bill Dubuque
    May 31 '15 at 22:18












  • The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm.
    – aristotle85
    May 31 '15 at 22:24








  • 1




    What results are discussed immediately before this?
    – Bill Dubuque
    May 31 '15 at 22:25


















  • It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $,17^{29},$ via exponentiation by repeated squaring and then notice right at the start that $,17^2equiv -1,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $,17^{-1}equiv -17equiv 12.,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise.
    – Bill Dubuque
    May 31 '15 at 22:18












  • The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm.
    – aristotle85
    May 31 '15 at 22:24








  • 1




    What results are discussed immediately before this?
    – Bill Dubuque
    May 31 '15 at 22:25
















It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $,17^{29},$ via exponentiation by repeated squaring and then notice right at the start that $,17^2equiv -1,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $,17^{-1}equiv -17equiv 12.,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise.
– Bill Dubuque
May 31 '15 at 22:18






It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $,17^{29},$ via exponentiation by repeated squaring and then notice right at the start that $,17^2equiv -1,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $,17^{-1}equiv -17equiv 12.,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise.
– Bill Dubuque
May 31 '15 at 22:18














The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm.
– aristotle85
May 31 '15 at 22:24






The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm.
– aristotle85
May 31 '15 at 22:24






1




1




What results are discussed immediately before this?
– Bill Dubuque
May 31 '15 at 22:25




What results are discussed immediately before this?
– Bill Dubuque
May 31 '15 at 22:25










3 Answers
3






active

oldest

votes


















2














The notes from Recitation 5 for this course describes using repeated squaring to reduce results given by Euler's Theorem. This is how I solved this problem:



$17^2$ = 289 ≡ 10 (mod 31)

$17^3$ = 4913 ≡ 15 (mod 31)

$17^6$ = $(17^3)^2$ ≡ $15^2$ = 225 ≡ 8 (mod 31)

$17^{12}$ = $(17^6)^2$ ≡ $8^2$ = 64 ≡ 2 (mod 31)



Then,



$17^{29}$ = $(17^{12})^2$ * $17^3$ * $17^2$ ≡ $(2)^2$ * 15 * 10 = 600 ≡ 11 (mod 31)



Thus,



17*11 ≡ 1 (mod 31)



So, the inverse of 17 modulo 31 in the range {1,...,30} is 11.






share|cite|improve this answer



















  • 1




    If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
    – David K
    Dec 31 '16 at 21:46



















1














Rather ad hoc, I note that $17 times 2 = 34 equiv 3$, which is a lot easier to deal with. Then $3 times 21 = 63 equiv 1$, so I look at $2 times 21 = 42 equiv 11$.



Sure enough, $17 times 11 = 187 equiv 1$.






share|cite|improve this answer





























    1














    I completed this question using the following steps:



    *Note: * Don't complete the computations on the right, the factorization is the part you are looking for!



    $17xequiv 1 pmod{31}$



    Step 1: $31 = 1 * 17 + 14 ... 14 = 31 - 1 * 17$



    Step 2: $17 = 1 * 14 + 3 ... 3 = 17 - 1 * 14$



    Step 3: $... ... 3 = 1 * 17 - 1 * [31 - 1 * 17]$



    Step 4: $... ... 3 = -1 * 31 + 2 * 17$



    Step 5: $14 = 4 * 3 + 2 ... 2 = 1 * 14 - 4 * 3$



    Step 6: $... ... 2 = 1 * [31 - 1 * 17] - 4 * [-1 * 31 + 2 * 17]$



    Step 7: $... ... 2 = 1*31 -1*17 + 4*31 - 8*17$



    Step 8: $... ... 2 = 5*31 -9*17$



    Step 9: $3 = 1 * 2 + 1 ... 1 = 1 * 3 - 1 * 2$



    Step 10: $... ... 1 = 1 * [-1 * 31 + 2 * 17] - 1 * [ 5 * 31 - 9 * 17]$



    Step 11: $... ... 1 = -1*31 + 2*17 -5*31 + 9*17$



    Step 12: $... ... 1 = -6*31 + 11*17$



    Finally,

    $11cdot17 equiv 1 pmod{31}$



    So the inverse of $17 !mod {31}$ is $11$






    share|cite|improve this answer



















    • 1




      Please, use MatJax next time you write formulas...
      – Ottavio Bartenor
      Dec 21 '15 at 20:22










    • @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
      – Thomas Tiveron
      Dec 21 '15 at 20:41










    • No problem, you're welcome!
      – Ottavio Bartenor
      Dec 21 '15 at 20:54











    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%2f1307082%2fuse-eulers-theorem-to-find-the-inverse-of-17-modulo-31-in-the-range-1-30%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    2














    The notes from Recitation 5 for this course describes using repeated squaring to reduce results given by Euler's Theorem. This is how I solved this problem:



    $17^2$ = 289 ≡ 10 (mod 31)

    $17^3$ = 4913 ≡ 15 (mod 31)

    $17^6$ = $(17^3)^2$ ≡ $15^2$ = 225 ≡ 8 (mod 31)

    $17^{12}$ = $(17^6)^2$ ≡ $8^2$ = 64 ≡ 2 (mod 31)



    Then,



    $17^{29}$ = $(17^{12})^2$ * $17^3$ * $17^2$ ≡ $(2)^2$ * 15 * 10 = 600 ≡ 11 (mod 31)



    Thus,



    17*11 ≡ 1 (mod 31)



    So, the inverse of 17 modulo 31 in the range {1,...,30} is 11.






    share|cite|improve this answer



















    • 1




      If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
      – David K
      Dec 31 '16 at 21:46
















    2














    The notes from Recitation 5 for this course describes using repeated squaring to reduce results given by Euler's Theorem. This is how I solved this problem:



    $17^2$ = 289 ≡ 10 (mod 31)

    $17^3$ = 4913 ≡ 15 (mod 31)

    $17^6$ = $(17^3)^2$ ≡ $15^2$ = 225 ≡ 8 (mod 31)

    $17^{12}$ = $(17^6)^2$ ≡ $8^2$ = 64 ≡ 2 (mod 31)



    Then,



    $17^{29}$ = $(17^{12})^2$ * $17^3$ * $17^2$ ≡ $(2)^2$ * 15 * 10 = 600 ≡ 11 (mod 31)



    Thus,



    17*11 ≡ 1 (mod 31)



    So, the inverse of 17 modulo 31 in the range {1,...,30} is 11.






    share|cite|improve this answer



















    • 1




      If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
      – David K
      Dec 31 '16 at 21:46














    2












    2








    2






    The notes from Recitation 5 for this course describes using repeated squaring to reduce results given by Euler's Theorem. This is how I solved this problem:



    $17^2$ = 289 ≡ 10 (mod 31)

    $17^3$ = 4913 ≡ 15 (mod 31)

    $17^6$ = $(17^3)^2$ ≡ $15^2$ = 225 ≡ 8 (mod 31)

    $17^{12}$ = $(17^6)^2$ ≡ $8^2$ = 64 ≡ 2 (mod 31)



    Then,



    $17^{29}$ = $(17^{12})^2$ * $17^3$ * $17^2$ ≡ $(2)^2$ * 15 * 10 = 600 ≡ 11 (mod 31)



    Thus,



    17*11 ≡ 1 (mod 31)



    So, the inverse of 17 modulo 31 in the range {1,...,30} is 11.






    share|cite|improve this answer














    The notes from Recitation 5 for this course describes using repeated squaring to reduce results given by Euler's Theorem. This is how I solved this problem:



    $17^2$ = 289 ≡ 10 (mod 31)

    $17^3$ = 4913 ≡ 15 (mod 31)

    $17^6$ = $(17^3)^2$ ≡ $15^2$ = 225 ≡ 8 (mod 31)

    $17^{12}$ = $(17^6)^2$ ≡ $8^2$ = 64 ≡ 2 (mod 31)



    Then,



    $17^{29}$ = $(17^{12})^2$ * $17^3$ * $17^2$ ≡ $(2)^2$ * 15 * 10 = 600 ≡ 11 (mod 31)



    Thus,



    17*11 ≡ 1 (mod 31)



    So, the inverse of 17 modulo 31 in the range {1,...,30} is 11.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 31 '16 at 20:33

























    answered Dec 31 '16 at 20:24









    Abhi Soni

    214




    214








    • 1




      If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
      – David K
      Dec 31 '16 at 21:46














    • 1




      If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
      – David K
      Dec 31 '16 at 21:46








    1




    1




    If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
    – David K
    Dec 31 '16 at 21:46




    If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 equiv 17cdot17^2 equiv 17cdot10 equiv 170 equiv 15 pmod{31}.$ and $2^2cdot 15cdot10equiv 2cdot(-1)cdot10 equiv -20equiv 11 pmod{31}.$
    – David K
    Dec 31 '16 at 21:46











    1














    Rather ad hoc, I note that $17 times 2 = 34 equiv 3$, which is a lot easier to deal with. Then $3 times 21 = 63 equiv 1$, so I look at $2 times 21 = 42 equiv 11$.



    Sure enough, $17 times 11 = 187 equiv 1$.






    share|cite|improve this answer


























      1














      Rather ad hoc, I note that $17 times 2 = 34 equiv 3$, which is a lot easier to deal with. Then $3 times 21 = 63 equiv 1$, so I look at $2 times 21 = 42 equiv 11$.



      Sure enough, $17 times 11 = 187 equiv 1$.






      share|cite|improve this answer
























        1












        1








        1






        Rather ad hoc, I note that $17 times 2 = 34 equiv 3$, which is a lot easier to deal with. Then $3 times 21 = 63 equiv 1$, so I look at $2 times 21 = 42 equiv 11$.



        Sure enough, $17 times 11 = 187 equiv 1$.






        share|cite|improve this answer












        Rather ad hoc, I note that $17 times 2 = 34 equiv 3$, which is a lot easier to deal with. Then $3 times 21 = 63 equiv 1$, so I look at $2 times 21 = 42 equiv 11$.



        Sure enough, $17 times 11 = 187 equiv 1$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 21 '15 at 20:17









        Brian Tung

        25.7k32553




        25.7k32553























            1














            I completed this question using the following steps:



            *Note: * Don't complete the computations on the right, the factorization is the part you are looking for!



            $17xequiv 1 pmod{31}$



            Step 1: $31 = 1 * 17 + 14 ... 14 = 31 - 1 * 17$



            Step 2: $17 = 1 * 14 + 3 ... 3 = 17 - 1 * 14$



            Step 3: $... ... 3 = 1 * 17 - 1 * [31 - 1 * 17]$



            Step 4: $... ... 3 = -1 * 31 + 2 * 17$



            Step 5: $14 = 4 * 3 + 2 ... 2 = 1 * 14 - 4 * 3$



            Step 6: $... ... 2 = 1 * [31 - 1 * 17] - 4 * [-1 * 31 + 2 * 17]$



            Step 7: $... ... 2 = 1*31 -1*17 + 4*31 - 8*17$



            Step 8: $... ... 2 = 5*31 -9*17$



            Step 9: $3 = 1 * 2 + 1 ... 1 = 1 * 3 - 1 * 2$



            Step 10: $... ... 1 = 1 * [-1 * 31 + 2 * 17] - 1 * [ 5 * 31 - 9 * 17]$



            Step 11: $... ... 1 = -1*31 + 2*17 -5*31 + 9*17$



            Step 12: $... ... 1 = -6*31 + 11*17$



            Finally,

            $11cdot17 equiv 1 pmod{31}$



            So the inverse of $17 !mod {31}$ is $11$






            share|cite|improve this answer



















            • 1




              Please, use MatJax next time you write formulas...
              – Ottavio Bartenor
              Dec 21 '15 at 20:22










            • @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
              – Thomas Tiveron
              Dec 21 '15 at 20:41










            • No problem, you're welcome!
              – Ottavio Bartenor
              Dec 21 '15 at 20:54
















            1














            I completed this question using the following steps:



            *Note: * Don't complete the computations on the right, the factorization is the part you are looking for!



            $17xequiv 1 pmod{31}$



            Step 1: $31 = 1 * 17 + 14 ... 14 = 31 - 1 * 17$



            Step 2: $17 = 1 * 14 + 3 ... 3 = 17 - 1 * 14$



            Step 3: $... ... 3 = 1 * 17 - 1 * [31 - 1 * 17]$



            Step 4: $... ... 3 = -1 * 31 + 2 * 17$



            Step 5: $14 = 4 * 3 + 2 ... 2 = 1 * 14 - 4 * 3$



            Step 6: $... ... 2 = 1 * [31 - 1 * 17] - 4 * [-1 * 31 + 2 * 17]$



            Step 7: $... ... 2 = 1*31 -1*17 + 4*31 - 8*17$



            Step 8: $... ... 2 = 5*31 -9*17$



            Step 9: $3 = 1 * 2 + 1 ... 1 = 1 * 3 - 1 * 2$



            Step 10: $... ... 1 = 1 * [-1 * 31 + 2 * 17] - 1 * [ 5 * 31 - 9 * 17]$



            Step 11: $... ... 1 = -1*31 + 2*17 -5*31 + 9*17$



            Step 12: $... ... 1 = -6*31 + 11*17$



            Finally,

            $11cdot17 equiv 1 pmod{31}$



            So the inverse of $17 !mod {31}$ is $11$






            share|cite|improve this answer



















            • 1




              Please, use MatJax next time you write formulas...
              – Ottavio Bartenor
              Dec 21 '15 at 20:22










            • @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
              – Thomas Tiveron
              Dec 21 '15 at 20:41










            • No problem, you're welcome!
              – Ottavio Bartenor
              Dec 21 '15 at 20:54














            1












            1








            1






            I completed this question using the following steps:



            *Note: * Don't complete the computations on the right, the factorization is the part you are looking for!



            $17xequiv 1 pmod{31}$



            Step 1: $31 = 1 * 17 + 14 ... 14 = 31 - 1 * 17$



            Step 2: $17 = 1 * 14 + 3 ... 3 = 17 - 1 * 14$



            Step 3: $... ... 3 = 1 * 17 - 1 * [31 - 1 * 17]$



            Step 4: $... ... 3 = -1 * 31 + 2 * 17$



            Step 5: $14 = 4 * 3 + 2 ... 2 = 1 * 14 - 4 * 3$



            Step 6: $... ... 2 = 1 * [31 - 1 * 17] - 4 * [-1 * 31 + 2 * 17]$



            Step 7: $... ... 2 = 1*31 -1*17 + 4*31 - 8*17$



            Step 8: $... ... 2 = 5*31 -9*17$



            Step 9: $3 = 1 * 2 + 1 ... 1 = 1 * 3 - 1 * 2$



            Step 10: $... ... 1 = 1 * [-1 * 31 + 2 * 17] - 1 * [ 5 * 31 - 9 * 17]$



            Step 11: $... ... 1 = -1*31 + 2*17 -5*31 + 9*17$



            Step 12: $... ... 1 = -6*31 + 11*17$



            Finally,

            $11cdot17 equiv 1 pmod{31}$



            So the inverse of $17 !mod {31}$ is $11$






            share|cite|improve this answer














            I completed this question using the following steps:



            *Note: * Don't complete the computations on the right, the factorization is the part you are looking for!



            $17xequiv 1 pmod{31}$



            Step 1: $31 = 1 * 17 + 14 ... 14 = 31 - 1 * 17$



            Step 2: $17 = 1 * 14 + 3 ... 3 = 17 - 1 * 14$



            Step 3: $... ... 3 = 1 * 17 - 1 * [31 - 1 * 17]$



            Step 4: $... ... 3 = -1 * 31 + 2 * 17$



            Step 5: $14 = 4 * 3 + 2 ... 2 = 1 * 14 - 4 * 3$



            Step 6: $... ... 2 = 1 * [31 - 1 * 17] - 4 * [-1 * 31 + 2 * 17]$



            Step 7: $... ... 2 = 1*31 -1*17 + 4*31 - 8*17$



            Step 8: $... ... 2 = 5*31 -9*17$



            Step 9: $3 = 1 * 2 + 1 ... 1 = 1 * 3 - 1 * 2$



            Step 10: $... ... 1 = 1 * [-1 * 31 + 2 * 17] - 1 * [ 5 * 31 - 9 * 17]$



            Step 11: $... ... 1 = -1*31 + 2*17 -5*31 + 9*17$



            Step 12: $... ... 1 = -6*31 + 11*17$



            Finally,

            $11cdot17 equiv 1 pmod{31}$



            So the inverse of $17 !mod {31}$ is $11$







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Dec 21 '15 at 20:38









            Ottavio Bartenor

            5421517




            5421517










            answered Dec 21 '15 at 20:12









            Thomas Tiveron

            114




            114








            • 1




              Please, use MatJax next time you write formulas...
              – Ottavio Bartenor
              Dec 21 '15 at 20:22










            • @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
              – Thomas Tiveron
              Dec 21 '15 at 20:41










            • No problem, you're welcome!
              – Ottavio Bartenor
              Dec 21 '15 at 20:54














            • 1




              Please, use MatJax next time you write formulas...
              – Ottavio Bartenor
              Dec 21 '15 at 20:22










            • @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
              – Thomas Tiveron
              Dec 21 '15 at 20:41










            • No problem, you're welcome!
              – Ottavio Bartenor
              Dec 21 '15 at 20:54








            1




            1




            Please, use MatJax next time you write formulas...
            – Ottavio Bartenor
            Dec 21 '15 at 20:22




            Please, use MatJax next time you write formulas...
            – Ottavio Bartenor
            Dec 21 '15 at 20:22












            @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
            – Thomas Tiveron
            Dec 21 '15 at 20:41




            @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again.
            – Thomas Tiveron
            Dec 21 '15 at 20:41












            No problem, you're welcome!
            – Ottavio Bartenor
            Dec 21 '15 at 20:54




            No problem, you're welcome!
            – Ottavio Bartenor
            Dec 21 '15 at 20:54


















            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%2f1307082%2fuse-eulers-theorem-to-find-the-inverse-of-17-modulo-31-in-the-range-1-30%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

            Questions related to Moebius Transform of Characteristic Function of the Primes

            Image
            2 $begingroup$ Consider the function defined in (1) below related to the fundamental prime counting function $pi(x)$ . Note that A143519(n) is not multiplicative. (1) $quad f(x)=sumlimits_{n=1}^{x}A143519(n)$ https://oeis.org/A143519 The following plot illustrates $f(x)$ defined in formula (1) above. Figure (1) : Illustration of $f(x)$ defined in formula (1) The integer zeros of $f(x)$ for $xle 10,000$ are listed in (2) below. (2) $quad$ {1,6,9,12,19,30,79,80,81,116,193,201,287,288,291,668,673,679,680,685,686,1109} The zero crossings of $f(x)$ for $xle 10,000$ where $f(x)$ doesn't settle at zero are listed in (3) below. (3) $quad$ {14,21,33,114,115,118,195,286,290,295,442,445,665,667,670,671,678,682} Question (1) : Does $f(x)$ have a finite number of integer zeros, and if so ...
            Read more

            List of scandals in India

            Image
            List of scandals in India From Wikipedia, the free encyclopedia Jump to navigation Jump to search This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries. This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages) This article has an unclear citation style . The references used may be made clearer with a different or consistent style of citation and footnoting. ( January 2014 ) (Learn how and when to remove this template message) This list is in reverse order. As a consequence it appears to be slanted towards recent events. Please try to keep recent events in historical perspective and add more content related to non-recent events. ( May 2013 ) (Learn how and when to remove this template message) ...
            Read more

            Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

            Image
            0 1 What exactly does the error message beginning with E: mean? I assume it has to do with the file structure on Ubuntu-on-Windows, but what exactly? The following package was automatically installed and is no longer required: os-prober Use 'apt-get autoremove' to remove it. The following extra packages will be installed: libxslt1.1 The following NEW packages will be installed: libxslt1.1 xmlstarlet 0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded. Need to get 435 kB of archives. After this operation, 1023 kB of additional disk space will be used. Get:1 http://archive.ubuntu.com/ubuntu/ trusty/main libxslt1.1 amd64 1.1.28-2build1 [145 kB] Get:2 http://archive.ubuntu.com/ubuntu/ trusty/universe xmlstarlet amd64 1.5.0-1 [290 kB] ...
            Read more