0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What exactly is the problem? $\endgroup$ – Jaroslaw Matlak Jul 10 '18 at 13:16
  • $\begingroup$ @JaroslawMatlak I need to find the value of $k$ for $l=4$ and $n=4m+1$ satisfying the congruence relation. $\endgroup$ – monalisa Jul 10 '18 at 13:23
  • 1
    $\begingroup$ Try $k=9$. Have you tried the Chinese remainder theorem? $\endgroup$ – Jaroslaw Matlak Jul 10 '18 at 13:25
  • $\begingroup$ Actually I am new to number theory. $\endgroup$ – monalisa Jul 10 '18 at 16:26
  • $\begingroup$ 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][1]. [1]: mathworld.wolfram.com/TotientFunction.html $\endgroup$ – Cleyton Muto Jul 18 '18 at 12:36
2
+50
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +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$$ $\endgroup$ – gandalf61 Jul 13 '18 at 9:43
  • $\begingroup$ Alex can you explain how you got the step $k \equiv \frac{1}{4} \equiv \frac{1 + an}{4} \pmod{n}$. Please . $\endgroup$ – monalisa Jul 23 '18 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.