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

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

Answer 1

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

Answer 2

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.