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$
7
  • 1
    $\begingroup$ What exactly is the problem? $\endgroup$ Jul 10, 2018 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, 2018 at 13:23
  • 1
    $\begingroup$ Try $k=9$. Have you tried the Chinese remainder theorem? $\endgroup$ Jul 10, 2018 at 13:25
  • $\begingroup$ Actually I am new to number theory. $\endgroup$
    – monalisa
    Jul 10, 2018 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$ Jul 18, 2018 at 12:36

1 Answer 1

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

$\endgroup$
2
  • $\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, 2018 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, 2018 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .