# 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 $$kl\equiv 1 \pmod n$$? Any hint or suggestion is welcome. Thanks for your kind help.

• Not following. What is given and what are you looking for? For a fixed $n$ there are many pairs of integers that multiply to $1\pmod n$. Indeed, for any $k$ with $\gcd(n,k)=1$ we can find an $l$ with $kl\equiv 1 \pmod n$.
– lulu
Dec 17, 2018 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$. Dec 17, 2018 at 11:44
• So...you are given $l=2$ and you are given an odd $n$. Then, yes. $2\times \frac {n+1}2\equiv 1 \pmod n$. And, yes, that value is unique $\pmod n$ . If there were two then $lk_1\equiv lk_2 \pmod n\implies l(k_1-k_2)\equiv 0 \implies k_1\equiv k_2$ since $\gcd(l,n)=1$.
– lulu
Dec 17, 2018 at 11:48
• @lulu. Oh...That means we have only unique value of $k$. Can we do it for other values of $l$, like $l\neq 2$, where $l$ is written in terms of $n$? Dec 17, 2018 at 11:50
• @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. Dec 17, 2018 at 14:45

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

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.. Dec 26, 2018 at 18:58