Solution of a congruence problem in number theory

Question

I was solving the following problem in number theory.

Given integers $k,l$ relatively prime to integer $n>3$ such that $kl\equiv1\pmod {n}$, where $n$ takes the form $n=4m,4m+1,4m+2$, and $4m+3$ for some positive integer $m$.

I was trying to find the value of $k$ for particular values of $l$ and $n$.

I assumed $l = 4$. Now, I need to find what values $k$ can attain to satisfy the above assumptions.

My attempt:

Since $l=4$ and it is relatively prime to $n$ then $n$ can not be $4m$ and $4m+2$. In my first case I considered $l=4$ and $n=4m+1$.

Now, since $k$ is relatively prime to $n$, $k$ will take values $4m$, $4m+2$, and few values of $4m+3$.

For example, I took the case where $l=4$, $n=4m+1$, and $k=4m$. This must satisfy $kl\equiv1\pmod {n}$. So I get

$$4(4m)\equiv1\pmod{(4m+1)}.$$

From here onwards, I am unable to proceed to solve and find the generalized value of $k$ for $l=4$ only for this problem. Can anyone help me in finding the solution? Thanks a lot for your help.

Answer 1

For $l = 4$, $(n, l) = 1$ requires that $2 \not\mid n$, i.e. $n \equiv 1, 3 \pmod{4}$. Because $(n, 4) = 1$, then$$ 4k \equiv 1 \pmod{n} \Longrightarrow k \equiv \frac{1}{4} \equiv \frac{1 + an}{4} \pmod{n}, $$ where $a$ is an arbitrary integer. In particular,

1. If $n = 4m + 1 \equiv 1 \pmod{4}$, then$$ 0 \equiv 1 + an \equiv 1 + a \pmod{4} \Longrightarrow a \equiv -1 \equiv 3 \pmod{4}, $$ thus$$ k \equiv \frac{1 + 3n}{4} \equiv 3m + 1 \pmod{n}. $$
2. If $n = 4m + 3 \equiv 3 \pmod{4}$, then$$ 0 \equiv 1 + an \equiv 1 + 3a \pmod{4} \Longrightarrow a \equiv \frac{-1}{3} \equiv \frac{-1 + 4}{3} \equiv 1 \pmod{4}, $$ thus$$ k \equiv \frac{1 + n}{4} \equiv m + 1 \pmod{n}.$$