Number theory : values of $l$, $k$; $k$ and $l$ are relatively prime to $n$ with $kl equiv 1 pmod n$.
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
|
show 1 more comment
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
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
|
show 1 more comment
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
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
number-theory elementary-number-theory proof-writing modular-arithmetic
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
|
show 1 more comment
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
|
show 1 more comment
2 Answers
2
active
oldest
votes
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}$.
add a comment |
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.
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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}$.
add a comment |
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}$.
add a comment |
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}$.
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}$.
edited Dec 29 '18 at 4:53
answered Dec 28 '18 at 8:22
Haran
810322
810322
add a comment |
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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