Intereting Posts

Let V denote the Klein 4-group. Show that $\text{Aut} (V)$ is isomorphic to $S_3$
Euler-Lagrange equations of the Lagrangian related to Maxwell's equations
Is complex analysis more “real” than real analysis?
Prove that there exists a Borel measurable function $h: \mathbb R \to \mathbb R$ such that $g= h\circ f$.
Proving an equality involving compositions of an integer
Topology: Proof that a finitely generated cone is closed
Norm of the product of two regular ideals of an order of an algebraic number field
Choose 100 numbers from 1~200 (one less than 16) – prove one is divisible by another!
Showing the countable direct product of $\mathbb{Z}$ is not projective
Prove $\alpha \in\mathbb R$ is irrational, when $\cos(\alpha \pi) = \frac{1}{3}$
How many prime numbers are known?
An equation of form $x^{2}+ax+b=0$ might have infinite amount of solutions in a ring $(R,+,\cdot)$
Operators such that $T\circ S=I$ but $S\circ T\neq I$.
Prove no existing a smooth function satisfying … related to Morse Theory
Is there a way to solve for an unknown in a factorial?

I need to find out the modular inverse of 5(mod 11), I know the answer is 9 and got the following so far and don’t understand how to than get the answer. I know how to get the answer for a larger one such as 27(mod 392) but am stuck because they are both low numbers.

11=5 (2)+1

5=1 (5)

- Is my shorter expression for $ s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?
- $\mathbb Z_p^*$ is a group.
- How to divide natural number N into M nearly equal summands?
- Prove Euler's Theorem when the integers are not relatively prime
- Given dividend and divisor, can we know the length of nonrepeating part and repeating part?
- solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$

- How to find the quotient group $Z_{1023}^*/\langle 2\rangle$?
- Modulus of Fraction
- Do inequations exist with congruences?
- How to find the solutions for the n-th root of unity in modular arithmetic?
- How to find the last digit of $3^{1000}$?
- Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?
- $n^2 + 3n +5$ is not divisible by $121$
- Frog Jump Problem
- Is there a quick way to find the remainder when this determinant is divided by $5$?
- Chinese Remainder Theorem and linear congruences

In finding a modular inverse, you are trying to solve the modular equation

$$

ax\equiv 1\pmod n.

$$

Ordinarily, you use the Extended Euclidean Algorithm for this to solve the equation $ax+ny=1$. If the numbers $a$, and $n$ are small, then simple trial and error is probably just as fast or faster.

For your example, we have $a=5$ and $n=11$, which means would could just use trial and error.

\begin{align}

1\cdot 5 &\equiv 5\\

2\cdot 5 &\equiv 10\\

3\cdot 5 &\equiv 15\equiv 4 \\

4\cdot 5 &\equiv 20\equiv -2\\

5\cdot 5 &\equiv 25\equiv 3 \\

6\cdot 5 &\equiv 30\equiv -3 \\

7\cdot 5 &\equiv 35\equiv 2 \\

8\cdot 5 &\equiv 40\equiv -4 \\

9\cdot 5 &\equiv 45\equiv 1 \\

10\cdot 5 &\equiv 50\equiv -5 \\

\end{align}

Since $9\cdot 5 \equiv 1$ then we have found the modular inverse to be 9.

When looking at those numbers on the far right side, keep in mind that any multiple of 11 made be added or subtracted to the modulus and it is still equivalent. That is, $-3\equiv 30\equiv 8$ since $-3+3(11)=30$ and $8+2(11)=30$.

**Hint** $\ $ mod $\,ab\!+\!1\!:\,\, ab \equiv -1 \,\Rightarrow\, a(-b) \equiv 1.\ $ Yours is $\,a,b = 5,2.$

Generally one can use the *Extended Euclidean Algorithm* to compute modular inverses (above is an optimization of the single-step case). Here is a convenient way to execute the algorithm.

You can use your work to get $1=11-5(2)=11+5(-2)$,

so an inverse of 5 (mod 11) is given by $-2\equiv9\pmod {11}$.

**Here is a piece of C code that you might find useful:**

```
int Inverse(int n,int a)
{
int x1 = 1;
int x2 = 0;
int y1 = 0;
int y2 = 1;
int r1 = n;
int r2 = a;
while (r2 != 0)
{
int r3 = r1%r2;
int q3 = r1/r2;
int x3 = x1-q3*x2;
int y3 = y1-q3*y2;
x1 = x2;
x2 = x3;
y1 = y2;
y2 = y3;
r1 = r2;
r2 = r3;
}
return y1>0? y1:y1+n;
}
```

Calling `Inverse(11,5)`

returns 9.

Calling `Inverse(392,27)`

returns 363.

- Bound of a complex-valued function
- Do these vectors form a basis?
- Is compactness a stronger form of continuity?
- Gradient is NOT the direction that points to the minimum or maximum
- Tangent sheaf of a (specific) nodal curve
- expected length of broken stick
- Conservation of mass in hyperbolic PDE
- Non-linear SDE: how to?
- Can a vector subspace have a unique complement in absence of choice?
- Non-Symmetric Positive Definite Matrices
- How can you find $P(\frac{X}{Y-X}<0)$ if $X\sim Geometric(p)$ and $Y\sim Bernoulli(p)$
- Does a non-trivial solution exist for $f'(x)=f(f(x))$?
- The completion of a separable inner product space is a separable Hilbert space
- What is the relation between weak convergence of measures and weak convergence from functional analysis
- If the graphs of $f(x)$ and $f^{-1}(x)$ intersect at an odd number of points, is at least one point on the line $y=x$?