Number theory : values of $l$, $k$; $k$ and $l$ are relatively prime to $n$ with $kl equiv 1 pmod n$.












0














For some given positive integers $n$, $l$, and $k$, $n$ is odd, I was looking for the values of $l$ and $k$ such that both $k$ and $l$ are relatively prime to $n$ and also satisfy
$kl equiv 1 pmod n$. I got one such example given below.



My attempt (Trial): One case.



I took $l = 2$ and $k = frac{n+1}{2}$.



Clearly, both $2$ and $ frac{n+1}{2}$ are relatively prime to $n$.



Also, $2.(frac{n+1}{2}) equiv 1 pmod n$.



My Doubt (edited the question): For what pairs of $k$ and $l$ such that both are relatively prime to $n$, we may get $klequiv 1 pmod n$? Any hint or suggestion is welcome. Thanks for your kind help.










share|cite|improve this question




















  • 2




    Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1pmod n$. Indeed, for any $k$ with $gcd(n,k)=1$ we can find an $l$ with $klequiv 1 pmod n$.
    – lulu
    Dec 17 '18 at 11:35












  • @lulu For particular value of $l$, i.e., $l=2$, I need the values of $k$ satisfying the given relation. I don't want the generalized thing, just for $l = 2$.
    – monalisa
    Dec 17 '18 at 11:44












  • So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2times frac {n+1}2equiv 1 pmod n$. And, yes, that value is unique $pmod n$ . If there were two then $lk_1equiv lk_2 pmod nimplies l(k_1-k_2)equiv 0 implies k_1equiv k_2$ since $gcd(l,n)=1$.
    – lulu
    Dec 17 '18 at 11:48










  • @lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $lneq 2$, where $l$ is written in terms of $n$?
    – monalisa
    Dec 17 '18 at 11:50








  • 1




    @monalisa Yes, $,k equiv ell^{-1} equiv dfrac{1-n,(n^{-1}bmod ell)}{ell}pmod{! n} $ where the latter quotient is exact in $,Bbb Z. $ For further details see inverse reciprocity.
    – Bill Dubuque
    Dec 17 '18 at 14:45


















0














For some given positive integers $n$, $l$, and $k$, $n$ is odd, I was looking for the values of $l$ and $k$ such that both $k$ and $l$ are relatively prime to $n$ and also satisfy
$kl equiv 1 pmod n$. I got one such example given below.



My attempt (Trial): One case.



I took $l = 2$ and $k = frac{n+1}{2}$.



Clearly, both $2$ and $ frac{n+1}{2}$ are relatively prime to $n$.



Also, $2.(frac{n+1}{2}) equiv 1 pmod n$.



My Doubt (edited the question): For what pairs of $k$ and $l$ such that both are relatively prime to $n$, we may get $klequiv 1 pmod n$? Any hint or suggestion is welcome. Thanks for your kind help.










share|cite|improve this question




















  • 2




    Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1pmod n$. Indeed, for any $k$ with $gcd(n,k)=1$ we can find an $l$ with $klequiv 1 pmod n$.
    – lulu
    Dec 17 '18 at 11:35












  • @lulu For particular value of $l$, i.e., $l=2$, I need the values of $k$ satisfying the given relation. I don't want the generalized thing, just for $l = 2$.
    – monalisa
    Dec 17 '18 at 11:44












  • So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2times frac {n+1}2equiv 1 pmod n$. And, yes, that value is unique $pmod n$ . If there were two then $lk_1equiv lk_2 pmod nimplies l(k_1-k_2)equiv 0 implies k_1equiv k_2$ since $gcd(l,n)=1$.
    – lulu
    Dec 17 '18 at 11:48










  • @lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $lneq 2$, where $l$ is written in terms of $n$?
    – monalisa
    Dec 17 '18 at 11:50








  • 1




    @monalisa Yes, $,k equiv ell^{-1} equiv dfrac{1-n,(n^{-1}bmod ell)}{ell}pmod{! n} $ where the latter quotient is exact in $,Bbb Z. $ For further details see inverse reciprocity.
    – Bill Dubuque
    Dec 17 '18 at 14:45
















0












0








0







For some given positive integers $n$, $l$, and $k$, $n$ is odd, I was looking for the values of $l$ and $k$ such that both $k$ and $l$ are relatively prime to $n$ and also satisfy
$kl equiv 1 pmod n$. I got one such example given below.



My attempt (Trial): One case.



I took $l = 2$ and $k = frac{n+1}{2}$.



Clearly, both $2$ and $ frac{n+1}{2}$ are relatively prime to $n$.



Also, $2.(frac{n+1}{2}) equiv 1 pmod n$.



My Doubt (edited the question): For what pairs of $k$ and $l$ such that both are relatively prime to $n$, we may get $klequiv 1 pmod n$? Any hint or suggestion is welcome. Thanks for your kind help.










share|cite|improve this question















For some given positive integers $n$, $l$, and $k$, $n$ is odd, I was looking for the values of $l$ and $k$ such that both $k$ and $l$ are relatively prime to $n$ and also satisfy
$kl equiv 1 pmod n$. I got one such example given below.



My attempt (Trial): One case.



I took $l = 2$ and $k = frac{n+1}{2}$.



Clearly, both $2$ and $ frac{n+1}{2}$ are relatively prime to $n$.



Also, $2.(frac{n+1}{2}) equiv 1 pmod n$.



My Doubt (edited the question): For what pairs of $k$ and $l$ such that both are relatively prime to $n$, we may get $klequiv 1 pmod n$? Any hint or suggestion is welcome. Thanks for your kind help.







number-theory elementary-number-theory proof-writing modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 17 '18 at 12:09

























asked Dec 17 '18 at 11:32









monalisa

1,20411937




1,20411937








  • 2




    Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1pmod n$. Indeed, for any $k$ with $gcd(n,k)=1$ we can find an $l$ with $klequiv 1 pmod n$.
    – lulu
    Dec 17 '18 at 11:35












  • @lulu For particular value of $l$, i.e., $l=2$, I need the values of $k$ satisfying the given relation. I don't want the generalized thing, just for $l = 2$.
    – monalisa
    Dec 17 '18 at 11:44












  • So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2times frac {n+1}2equiv 1 pmod n$. And, yes, that value is unique $pmod n$ . If there were two then $lk_1equiv lk_2 pmod nimplies l(k_1-k_2)equiv 0 implies k_1equiv k_2$ since $gcd(l,n)=1$.
    – lulu
    Dec 17 '18 at 11:48










  • @lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $lneq 2$, where $l$ is written in terms of $n$?
    – monalisa
    Dec 17 '18 at 11:50








  • 1




    @monalisa Yes, $,k equiv ell^{-1} equiv dfrac{1-n,(n^{-1}bmod ell)}{ell}pmod{! n} $ where the latter quotient is exact in $,Bbb Z. $ For further details see inverse reciprocity.
    – Bill Dubuque
    Dec 17 '18 at 14:45
















  • 2




    Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1pmod n$. Indeed, for any $k$ with $gcd(n,k)=1$ we can find an $l$ with $klequiv 1 pmod n$.
    – lulu
    Dec 17 '18 at 11:35












  • @lulu For particular value of $l$, i.e., $l=2$, I need the values of $k$ satisfying the given relation. I don't want the generalized thing, just for $l = 2$.
    – monalisa
    Dec 17 '18 at 11:44












  • So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2times frac {n+1}2equiv 1 pmod n$. And, yes, that value is unique $pmod n$ . If there were two then $lk_1equiv lk_2 pmod nimplies l(k_1-k_2)equiv 0 implies k_1equiv k_2$ since $gcd(l,n)=1$.
    – lulu
    Dec 17 '18 at 11:48










  • @lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $lneq 2$, where $l$ is written in terms of $n$?
    – monalisa
    Dec 17 '18 at 11:50








  • 1




    @monalisa Yes, $,k equiv ell^{-1} equiv dfrac{1-n,(n^{-1}bmod ell)}{ell}pmod{! n} $ where the latter quotient is exact in $,Bbb Z. $ For further details see inverse reciprocity.
    – Bill Dubuque
    Dec 17 '18 at 14:45










2




2




Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1pmod n$. Indeed, for any $k$ with $gcd(n,k)=1$ we can find an $l$ with $klequiv 1 pmod n$.
– lulu
Dec 17 '18 at 11:35






Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1pmod n$. Indeed, for any $k$ with $gcd(n,k)=1$ we can find an $l$ with $klequiv 1 pmod n$.
– lulu
Dec 17 '18 at 11:35














@lulu For particular value of $l$, i.e., $l=2$, I need the values of $k$ satisfying the given relation. I don't want the generalized thing, just for $l = 2$.
– monalisa
Dec 17 '18 at 11:44






@lulu For particular value of $l$, i.e., $l=2$, I need the values of $k$ satisfying the given relation. I don't want the generalized thing, just for $l = 2$.
– monalisa
Dec 17 '18 at 11:44














So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2times frac {n+1}2equiv 1 pmod n$. And, yes, that value is unique $pmod n$ . If there were two then $lk_1equiv lk_2 pmod nimplies l(k_1-k_2)equiv 0 implies k_1equiv k_2$ since $gcd(l,n)=1$.
– lulu
Dec 17 '18 at 11:48




So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2times frac {n+1}2equiv 1 pmod n$. And, yes, that value is unique $pmod n$ . If there were two then $lk_1equiv lk_2 pmod nimplies l(k_1-k_2)equiv 0 implies k_1equiv k_2$ since $gcd(l,n)=1$.
– lulu
Dec 17 '18 at 11:48












@lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $lneq 2$, where $l$ is written in terms of $n$?
– monalisa
Dec 17 '18 at 11:50






@lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $lneq 2$, where $l$ is written in terms of $n$?
– monalisa
Dec 17 '18 at 11:50






1




1




@monalisa Yes, $,k equiv ell^{-1} equiv dfrac{1-n,(n^{-1}bmod ell)}{ell}pmod{! n} $ where the latter quotient is exact in $,Bbb Z. $ For further details see inverse reciprocity.
– Bill Dubuque
Dec 17 '18 at 14:45






@monalisa Yes, $,k equiv ell^{-1} equiv dfrac{1-n,(n^{-1}bmod ell)}{ell}pmod{! n} $ where the latter quotient is exact in $,Bbb Z. $ For further details see inverse reciprocity.
– Bill Dubuque
Dec 17 '18 at 14:45












2 Answers
2






active

oldest

votes


















1





+50









For any number $k$ relatively prime to $n$, there exists a unique $l$ modulo $n$ such that $kl equiv 1 pmod{n}$. Consider all remainders $x$ such that $x$ is relatively prime to $n$. As $x$ is relatively prime to $n$, so is $kx$. Now: $$ki equiv kj pmod{n} implies i equiv j pmod{n}$$
as I can divide by $k$ knowing that $gcd(k,n)=1$. Thus, for two distinct relatively prime remainders, $x$ and $y$, $kx$ and $ky$ themselves are distinct. Thus, if we multiply all distinct relatively prime remainders ${x_1,x_2,...,x_phi(n)}$ with $k$, we get distinct remainders ${kx_1,kx_2,...,kx_phi(n)}$. As there are only $phi(n)$ possible distinct remainders and one of them is $1$ as $gcd(1,n)=1$, we have one and only one value $l = x_y$ such that $kl equiv 1 pmod{n}$.



If $k$ is not relatively prime to $n$, i.e. if $gcd(k,n) neq 1$, then such $l$ will surely not exist as, of we assume the contrary, there will be $c>1$ such that $c mid k,n$ which would imply that $c mid 1$. Contradiction.



Such a unique value for $l$ for the given $k$ is known as its modular inverse modulo $n$. There aren't any general expressions for $k,l$ for a given $n$, but for given $k$ and $n$, we can find the value of $l$ by trial or by being a little more careful such as below:



Question : Find $l$ such that $7l equiv 1 pmod{19}$



Solution: We know that $7l equiv 1 pmod{19} implies 3(7l) equiv 3 pmod{19} implies 21l equiv 3 pmod{19}$



Then, we know that $21 equiv 2 pmod{19}$. Thus, $2l equiv 3 pmod{19}$. Now, to make the coefficient of $l$ as $1$, we know that $20 equiv 1 pmod{19}$ and $2 mid 20$. Thus, we can multiply both sides by $10$ :
$$2l equiv 3 pmod{19} implies 20l equiv 30 pmod{19} implies l equiv 11 pmod{19}$$



Thus, for $k equiv 7 pmod{19}$ , we have a unique inverse $l equiv 11 pmod{19}$.






share|cite|improve this answer































    1














    If you're familiar with the Bachet-Bezout theorem, note that, given $l perp n$, $kl equiv 1 iff k'l - 1 = nb iff k'l + nb = 1$. But such $k', b$ exists iff $rm{gcd}(k',n) = rm{gcd(l,n)} = 1$. To find such numbers, use the extended Euclidean algorithm.






    share|cite|improve this answer





















    • OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
      – Lucas Henrique
      Dec 26 '18 at 18:58











    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%2f3043835%2fnumber-theory-values-of-l-k-k-and-l-are-relatively-prime-to-n-with%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1





    +50









    For any number $k$ relatively prime to $n$, there exists a unique $l$ modulo $n$ such that $kl equiv 1 pmod{n}$. Consider all remainders $x$ such that $x$ is relatively prime to $n$. As $x$ is relatively prime to $n$, so is $kx$. Now: $$ki equiv kj pmod{n} implies i equiv j pmod{n}$$
    as I can divide by $k$ knowing that $gcd(k,n)=1$. Thus, for two distinct relatively prime remainders, $x$ and $y$, $kx$ and $ky$ themselves are distinct. Thus, if we multiply all distinct relatively prime remainders ${x_1,x_2,...,x_phi(n)}$ with $k$, we get distinct remainders ${kx_1,kx_2,...,kx_phi(n)}$. As there are only $phi(n)$ possible distinct remainders and one of them is $1$ as $gcd(1,n)=1$, we have one and only one value $l = x_y$ such that $kl equiv 1 pmod{n}$.



    If $k$ is not relatively prime to $n$, i.e. if $gcd(k,n) neq 1$, then such $l$ will surely not exist as, of we assume the contrary, there will be $c>1$ such that $c mid k,n$ which would imply that $c mid 1$. Contradiction.



    Such a unique value for $l$ for the given $k$ is known as its modular inverse modulo $n$. There aren't any general expressions for $k,l$ for a given $n$, but for given $k$ and $n$, we can find the value of $l$ by trial or by being a little more careful such as below:



    Question : Find $l$ such that $7l equiv 1 pmod{19}$



    Solution: We know that $7l equiv 1 pmod{19} implies 3(7l) equiv 3 pmod{19} implies 21l equiv 3 pmod{19}$



    Then, we know that $21 equiv 2 pmod{19}$. Thus, $2l equiv 3 pmod{19}$. Now, to make the coefficient of $l$ as $1$, we know that $20 equiv 1 pmod{19}$ and $2 mid 20$. Thus, we can multiply both sides by $10$ :
    $$2l equiv 3 pmod{19} implies 20l equiv 30 pmod{19} implies l equiv 11 pmod{19}$$



    Thus, for $k equiv 7 pmod{19}$ , we have a unique inverse $l equiv 11 pmod{19}$.






    share|cite|improve this answer




























      1





      +50









      For any number $k$ relatively prime to $n$, there exists a unique $l$ modulo $n$ such that $kl equiv 1 pmod{n}$. Consider all remainders $x$ such that $x$ is relatively prime to $n$. As $x$ is relatively prime to $n$, so is $kx$. Now: $$ki equiv kj pmod{n} implies i equiv j pmod{n}$$
      as I can divide by $k$ knowing that $gcd(k,n)=1$. Thus, for two distinct relatively prime remainders, $x$ and $y$, $kx$ and $ky$ themselves are distinct. Thus, if we multiply all distinct relatively prime remainders ${x_1,x_2,...,x_phi(n)}$ with $k$, we get distinct remainders ${kx_1,kx_2,...,kx_phi(n)}$. As there are only $phi(n)$ possible distinct remainders and one of them is $1$ as $gcd(1,n)=1$, we have one and only one value $l = x_y$ such that $kl equiv 1 pmod{n}$.



      If $k$ is not relatively prime to $n$, i.e. if $gcd(k,n) neq 1$, then such $l$ will surely not exist as, of we assume the contrary, there will be $c>1$ such that $c mid k,n$ which would imply that $c mid 1$. Contradiction.



      Such a unique value for $l$ for the given $k$ is known as its modular inverse modulo $n$. There aren't any general expressions for $k,l$ for a given $n$, but for given $k$ and $n$, we can find the value of $l$ by trial or by being a little more careful such as below:



      Question : Find $l$ such that $7l equiv 1 pmod{19}$



      Solution: We know that $7l equiv 1 pmod{19} implies 3(7l) equiv 3 pmod{19} implies 21l equiv 3 pmod{19}$



      Then, we know that $21 equiv 2 pmod{19}$. Thus, $2l equiv 3 pmod{19}$. Now, to make the coefficient of $l$ as $1$, we know that $20 equiv 1 pmod{19}$ and $2 mid 20$. Thus, we can multiply both sides by $10$ :
      $$2l equiv 3 pmod{19} implies 20l equiv 30 pmod{19} implies l equiv 11 pmod{19}$$



      Thus, for $k equiv 7 pmod{19}$ , we have a unique inverse $l equiv 11 pmod{19}$.






      share|cite|improve this answer


























        1





        +50







        1





        +50



        1




        +50




        For any number $k$ relatively prime to $n$, there exists a unique $l$ modulo $n$ such that $kl equiv 1 pmod{n}$. Consider all remainders $x$ such that $x$ is relatively prime to $n$. As $x$ is relatively prime to $n$, so is $kx$. Now: $$ki equiv kj pmod{n} implies i equiv j pmod{n}$$
        as I can divide by $k$ knowing that $gcd(k,n)=1$. Thus, for two distinct relatively prime remainders, $x$ and $y$, $kx$ and $ky$ themselves are distinct. Thus, if we multiply all distinct relatively prime remainders ${x_1,x_2,...,x_phi(n)}$ with $k$, we get distinct remainders ${kx_1,kx_2,...,kx_phi(n)}$. As there are only $phi(n)$ possible distinct remainders and one of them is $1$ as $gcd(1,n)=1$, we have one and only one value $l = x_y$ such that $kl equiv 1 pmod{n}$.



        If $k$ is not relatively prime to $n$, i.e. if $gcd(k,n) neq 1$, then such $l$ will surely not exist as, of we assume the contrary, there will be $c>1$ such that $c mid k,n$ which would imply that $c mid 1$. Contradiction.



        Such a unique value for $l$ for the given $k$ is known as its modular inverse modulo $n$. There aren't any general expressions for $k,l$ for a given $n$, but for given $k$ and $n$, we can find the value of $l$ by trial or by being a little more careful such as below:



        Question : Find $l$ such that $7l equiv 1 pmod{19}$



        Solution: We know that $7l equiv 1 pmod{19} implies 3(7l) equiv 3 pmod{19} implies 21l equiv 3 pmod{19}$



        Then, we know that $21 equiv 2 pmod{19}$. Thus, $2l equiv 3 pmod{19}$. Now, to make the coefficient of $l$ as $1$, we know that $20 equiv 1 pmod{19}$ and $2 mid 20$. Thus, we can multiply both sides by $10$ :
        $$2l equiv 3 pmod{19} implies 20l equiv 30 pmod{19} implies l equiv 11 pmod{19}$$



        Thus, for $k equiv 7 pmod{19}$ , we have a unique inverse $l equiv 11 pmod{19}$.






        share|cite|improve this answer














        For any number $k$ relatively prime to $n$, there exists a unique $l$ modulo $n$ such that $kl equiv 1 pmod{n}$. Consider all remainders $x$ such that $x$ is relatively prime to $n$. As $x$ is relatively prime to $n$, so is $kx$. Now: $$ki equiv kj pmod{n} implies i equiv j pmod{n}$$
        as I can divide by $k$ knowing that $gcd(k,n)=1$. Thus, for two distinct relatively prime remainders, $x$ and $y$, $kx$ and $ky$ themselves are distinct. Thus, if we multiply all distinct relatively prime remainders ${x_1,x_2,...,x_phi(n)}$ with $k$, we get distinct remainders ${kx_1,kx_2,...,kx_phi(n)}$. As there are only $phi(n)$ possible distinct remainders and one of them is $1$ as $gcd(1,n)=1$, we have one and only one value $l = x_y$ such that $kl equiv 1 pmod{n}$.



        If $k$ is not relatively prime to $n$, i.e. if $gcd(k,n) neq 1$, then such $l$ will surely not exist as, of we assume the contrary, there will be $c>1$ such that $c mid k,n$ which would imply that $c mid 1$. Contradiction.



        Such a unique value for $l$ for the given $k$ is known as its modular inverse modulo $n$. There aren't any general expressions for $k,l$ for a given $n$, but for given $k$ and $n$, we can find the value of $l$ by trial or by being a little more careful such as below:



        Question : Find $l$ such that $7l equiv 1 pmod{19}$



        Solution: We know that $7l equiv 1 pmod{19} implies 3(7l) equiv 3 pmod{19} implies 21l equiv 3 pmod{19}$



        Then, we know that $21 equiv 2 pmod{19}$. Thus, $2l equiv 3 pmod{19}$. Now, to make the coefficient of $l$ as $1$, we know that $20 equiv 1 pmod{19}$ and $2 mid 20$. Thus, we can multiply both sides by $10$ :
        $$2l equiv 3 pmod{19} implies 20l equiv 30 pmod{19} implies l equiv 11 pmod{19}$$



        Thus, for $k equiv 7 pmod{19}$ , we have a unique inverse $l equiv 11 pmod{19}$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 29 '18 at 4:53

























        answered Dec 28 '18 at 8:22









        Haran

        810322




        810322























            1














            If you're familiar with the Bachet-Bezout theorem, note that, given $l perp n$, $kl equiv 1 iff k'l - 1 = nb iff k'l + nb = 1$. But such $k', b$ exists iff $rm{gcd}(k',n) = rm{gcd(l,n)} = 1$. To find such numbers, use the extended Euclidean algorithm.






            share|cite|improve this answer





















            • OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
              – Lucas Henrique
              Dec 26 '18 at 18:58
















            1














            If you're familiar with the Bachet-Bezout theorem, note that, given $l perp n$, $kl equiv 1 iff k'l - 1 = nb iff k'l + nb = 1$. But such $k', b$ exists iff $rm{gcd}(k',n) = rm{gcd(l,n)} = 1$. To find such numbers, use the extended Euclidean algorithm.






            share|cite|improve this answer





















            • OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
              – Lucas Henrique
              Dec 26 '18 at 18:58














            1












            1








            1






            If you're familiar with the Bachet-Bezout theorem, note that, given $l perp n$, $kl equiv 1 iff k'l - 1 = nb iff k'l + nb = 1$. But such $k', b$ exists iff $rm{gcd}(k',n) = rm{gcd(l,n)} = 1$. To find such numbers, use the extended Euclidean algorithm.






            share|cite|improve this answer












            If you're familiar with the Bachet-Bezout theorem, note that, given $l perp n$, $kl equiv 1 iff k'l - 1 = nb iff k'l + nb = 1$. But such $k', b$ exists iff $rm{gcd}(k',n) = rm{gcd(l,n)} = 1$. To find such numbers, use the extended Euclidean algorithm.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Dec 18 '18 at 18:14









            Lucas Henrique

            968414




            968414












            • OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
              – Lucas Henrique
              Dec 26 '18 at 18:58


















            • OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
              – Lucas Henrique
              Dec 26 '18 at 18:58
















            OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
            – Lucas Henrique
            Dec 26 '18 at 18:58




            OP: the question has a bounty but I don't see what you do not understand to choose this a correct answer. This is literally the only choice..
            – Lucas Henrique
            Dec 26 '18 at 18:58


















            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%2f3043835%2fnumber-theory-values-of-l-k-k-and-l-are-relatively-prime-to-n-with%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

            Human spaceflight

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

            張江高科駅