+0

0
59
5

Let $n$ be a positive integer greater than or equal to $3$. Let $a,b$ be integers such that $ab$ is invertible modulo $n$ and $(ab)^{-1} \equiv 2$ (mod $n$). Given $a+b$ is invertible, what is the remainder when $(a+b)^{-1}(a^{-1}+b^{-1})$ is divided by $n$?

Jun 16, 2021

#1
0

The remainder is 4.

Jun 16, 2021
#2
0

Can you please elaborate and share how you got that solution?

Guest Jun 16, 2021
#3
+26117
+1

Let $$n$$ be a positive integer greater than or equal to $$3$$.

Let $$a,b$$ be integers such that $$ab$$ is invertible modulo $$n$$ and $$(ab)^{-1} \equiv 2 \pmod{n}$$.

Given $$a+b$$ is invertible, what is the remainder when $$(a+b)^{-1}(a^{-1}+b^{-1})$$ is divided by $$n$$?

Jun 17, 2021
#4
+287
+1

For brevity, all congruences below are taken modulo $n$.  $(ab)^{-1}\equiv 2$ means $2(ab)\equiv1$.  So we have $(2a)b\equiv a(2b)\equiv1$, meaning both $a$ and $b$ are invertible with $a^{-1}= 2b\bmod n$ and $b^{-1}=2a\bmod n$.  Thus,
\begin{eqnarray*}
(a+b)^{-1}(a^{-1}+b^{-1}) &\equiv& (a+b)^{-1}(2b+2a) \\
&\equiv& ((a+b)^{-1}(a+b))2 \\
&\equiv& 1\cdot 2 \\
&\equiv& 2.
\end{eqnarray*}

Jun 17, 2021
#5
+26117
+1

Let $$n$$ be a positive integer greater than or equal to $$3$$.
Let $$a,b$$ be integers such that $$ab$$ is invertible modulo $$n$$ and
$$(ab)^{-1} \equiv 2 \pmod {n}$$.
Given $$a+b$$ is invertible, what is the remainder when
$$(a+b)^{-1} \left(a^{-1}+b^{-1} \right)$$ is divided by $$n$$?

$$\begin{array}{|lrclcc|} \hline & && & \quad I. & \quad II. \\ & (ab)^{-1}=\dfrac{1}{ab} &\equiv& 2 \pmod{n} &| *a &| *b \\\\ \hline I. & \dfrac{a}{ab}&\equiv& 2a \pmod{n} \\ & \dfrac{1}{b} &\equiv& 2a \pmod{n} \\ & \mathbf{b^{-1}} &\equiv& \mathbf{2a \pmod{n}} \\\\ II. & \dfrac{b}{ab}&\equiv& 2b \pmod{n} \\ & \dfrac{1}{a} &\equiv& 2b \pmod{n} \\ & \mathbf{a^{-1}} &\equiv& \mathbf{2b \pmod{n}} \\ \hline \end{array}$$

$$\begin{array}{|rcll|} \hline (a+b)^{-1}(a^{-1}+b^{-1}) &\equiv& (a+b)^{-1}(2b+2a) \\ &\equiv& 2(a+b)^{-1}(b+a) \\ &\equiv& 2*\left(\dfrac{a+b}{a+b}\right) \\ &\equiv& 2*1 \\ \mathbf{ (a+b)^{-1}(a^{-1}+b^{-1}) } &\equiv& \mathbf{ 2 \pmod{n} }\\ \hline \end{array}$$

Jun 17, 2021
edited by heureka  Jun 17, 2021