Cfrgtkky

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.

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.