# Solution of a congruence problem in number theory

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.

• What exactly is the problem? – Jaroslaw Matlak Jul 10 '18 at 13:16
• @JaroslawMatlak I need to find the value of $k$ for $l=4$ and $n=4m+1$ satisfying the congruence relation. – monalisa Jul 10 '18 at 13:23
• Try $k=9$. Have you tried the Chinese remainder theorem? – Jaroslaw Matlak Jul 10 '18 at 13:25
• Actually I am new to number theory. – monalisa Jul 10 '18 at 16:26
• If $k$ and $l$ are relatively prime, such that $k\cdot l\equiv 1\;\left(mod\;n\right)$, then $k\equiv l^{\;\varphi\left(n\right)-1}\;\left(mod\;n\right)$ where $\varphi\left(n\right)$ is the [totient function]. : mathworld.wolfram.com/TotientFunction.html – Cleyton Muto Jul 18 '18 at 12:36

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}.$$
• +1. Look like a great answer to me. Examples : $$n=13, k=10, 4 \times 10 = 40 = 1 \mod 13$$ $$n=19, k=5, 4 \times 5 = 20 = 1 \mod 19$$ – gandalf61 Jul 13 '18 at 9:43
• Alex can you explain how you got the step $k \equiv \frac{1}{4} \equiv \frac{1 + an}{4} \pmod{n}$. Please . – monalisa Jul 23 '18 at 13:56