Find $a \in \mathbb Z$, which solves $11 \cdot a \equiv 1 \pmod {1247}$

Question

How would you solve the question (in the title)?

Can I apply your approach/solution (for the title question) also for: $13 \cdot a \equiv 1 \pmod {1337}$ and $69 \cdot a \equiv 8 \pmod {8008}$ etc.?

Answer 1

By Euclid division algorithm: $D = dq + r, r < d$

$D = 11a$

$d = 1247$

$r = 1$

Diophantine: $11a - 1247 q = 1$

Now, successive divisions for calculating gcd(1247, 11):

$1247 = 11 \cdot 113 + 4$

$11 = 4 \cdot 2 + 3$

$4 = 3 \cdot 1 + 1$

$a = a_0 + 1247 t, q = q_0 + 11t$

We take the remainders above:

$4 = 1247 - 11 \cdot 113 = 1247x + 11y$

$3 = 11 - 4 \cdot 2$

$1 = 4 - 3 \cdot 1 = (1247 - 11 \cdot 113) - (11 - 4 \cdot 2) \cdot 1$, rearrange and exchange $4$:

$1 = 1247 - 11 \cdot 114 + (1247 - 11 \cdot 113) \cdot 2$

$1 = 1247 \cdot 3 - 11 \cdot (114 + 113 \cdot 2)$

$1 = 1247 \cdot 3 - 11 \cdot 340 \Rightarrow a_0 = -340, q_0 = -3$

$11 (-340) - 1247 (-3) = 1$

$a \in \{-340 + 1247 t ; t \in \mathbb{Z} \} = \{..., -1587, -340, 907, 2154, ...\}$

---

$D = dq + r, r < d$

$D = 69a$

$d = 8008$

$r = 8$

$69a - 8008q = 8$

$8008 = 116 \cdot 69 + 4 \Rightarrow 4 = 8008 - 116 \cdot 69$

$69 = 17 \cdot 4 + 1 \Rightarrow 1 = 69 - 17 \cdot (8008 - 116 \cdot 69) = 69(+1973) - 8008(+17)$

Multiply by $8$:

$8 = 69(+15784) - 8008(+136)$

$a_0 = 15784 ; a = a_0 + 8008t \in \{8008t + 15784\} = \{..., -232, 7776, 15784, ... \}$

Memorize the steps to the test :-)

Answer 2

Use Bézout: with the Extended Euclidean algorithm, you get: $$-340\cdot 11+3\cdot 1247=1,\quad\mathrm{hence}\quad -340\cdot 11\equiv 1\mod 1247.$$

Answer 3

Hint $\ $ By $ $ Gauss's algorithm, $\,\ {\rm mod}\ 1247\!:\,\ \dfrac{1}{11}\equiv \dfrac{1}{11}\dfrac{113}{113}\equiv\dfrac{113}{-4}\equiv\dfrac{113+1247}{-4}\equiv -340$

More generally $\,1247 = 11(\color{#c00}{113})+4\,$ so above is case $\,\color{#c00}{j=113}\,$ of below

$\!\bmod 11\color{#c00}j+4\!:\,\ \dfrac{1}{11}\equiv \dfrac{j}{11j}\equiv \dfrac{12j+4}{-4}\equiv -(3j+1)\ $ again by Gauss and a twiddle.

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.