Intereting Posts

Are $T\mathbb{S}_2$ and $\mathbb{S}_2 \times \mathbb{R}^2$ different?
Function which is not in $L^2(R^n)$
Vakil 14.2.E: $L\approx O_X(div(s))$ for s a rational section.
Finding the limit of sequence
Primes $p$ such that $2$ is a primitive root modulo $p$ , where $p=4\cdot k^2+1$?
Can $\pi$ be a root of a polynomial under special cases?
Can a space $X$ be homeomorphic to its twofold product with itself, $X \times X$?
How to prove a limit exists using the $\epsilon$-$\delta$ definition of a limit
How to evaluate $\int_0^{2\pi}\frac{1-\alpha\cos{\theta}}{r'^3}d\theta$
Are there non-zero combinatorial games of odd order?
Prove that $ \lim_{n \to \infty}\frac{n}{\sqrt n!}=e$?
How to find the minimum/maximum distance of a point from elipse
Proving by induction that $2^n \le 2^{n+1}-2^{n-1} – 1$ . Does my proof make sense?
$\operatorname{Ann}_RA+\operatorname{Ann}_RB\subseteq\operatorname{Ann}_R\operatorname{Ext}^n_R(A,B)$?
The term “elliptic”

I am working through a review problem asking to find the inverse of

$4\bmod 9 $.

Through examples I know that I first need to verify that the gcd is equal to 1 and write it as a linear combination of 4 and 9 to find the inverse. I can do this in just one step:

```
gcd(4,9)
9 = 2 * 4 + 1
1 = 9 - 2 * 4
```

This would suggest that the inverse is 1 if I am understanding this correctly. However, the solution manual doesn’t show the work but says the LC should actually be

```
1 = 7 * 4 - 3 * 9
```

making the answer to the question 7.

- Can an odd perfect number be divisible by $101$?
- A formula for the least common multiple less than n?
- For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$.
- Power residue theorem without p-adic method
- When is $2^x+3^y$ a perfect square?
- Extended Euclidean Algorithm, what is our answer?

Can anyone explain to me what is going on here and how to properly find the inverse?

Thanks!

P.S. wish I could add tags for congruency, gcd, and inverse. I can’t believe their isn’t an inverse tag already 🙁

- Numbers are too large to show $65^{64}+64^{65}$ is not a prime
- $x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$
- Relation of modulo multiplicative inverses: if $m = x^{-1} \pmod y$, is there $n$ such that $n = y^{-1} \pmod x$?
- Prove $\frac{a^3+b^3+c^3}{3}\frac{a^7+b^7+c^7}{7} = \left(\frac{a^5+b^5+c^5}{5}\right)^2$ if $a+b+c=0$
- A combinatorial number theory question (pigeonhole principle)
- The last digit of $n^5-n$
- Solving simple congruences by hand
- Fibonacci Sequence problem. Prove that there are infinitely many prime numbers such that $p$ divides $F_{p-1}$
- $ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$?
- Can the sum of the first $n$ squares be a cube?

I know you’ve already gotten lots of responses, but instead of trying to fit responses into the comments under an answer I thought I’d just reiterate exactly *why* you need to do what you’re doing.

An inverse to $4 \mod 9$ is an integer $a$ such that $4a \equiv 1 \mod 9$. If we rewrite this, it means precisely that $9| (4a-1)$, or that there is another integer $b$ so that $9b = 4a-1$. What this says is that you need to find integer solutions to $4x-9y=1$. If you find that $x=a$ and $y=b$ works then $a$ is an inverse.

So what you do to solve something like this is run the Euclidean algorithm for $9$ and $4$, and then “reverse” the steps.

$9=4\cdot 2 + 1$, so it is actually over in 1 step in this case. Just subtract over to get $9-4\cdot 2 = 1$, or in the form we wrote it above $4\cdot (-2)-9\cdot (-1)=1$. So a solution is $x=-2$ and $y=-1$ and we said the $x$-value was the inverse, so the inverse is $-2\mod 9$.

Hopefully if you understand the process of why you’re doing these things, then if you get confused about which one is which on the final you can always just rederive it from these steps.

$-2$ is congruent to $7$ mod $9$. Your arithmetic steps are correct, but the conclusion should be that the congruence class of $-2$ is the inverse of $4$ mod $9$, and you probably want to use representatives in $\{1,2,3,4,5,6,7,8\}$ for your inverses, for simplicity, by adding appropriate multiples of $9$.

**HINT** $\ $ Congruences preserve inverses, i.e. $\rm\ A\equiv a\ \Rightarrow\ A^{-1}\equiv a^{-1}\:.\ $ This follows from the fact that congruences preserve products, i.e. it’s the special case $\rm\: AB \equiv 1\: $ in this **congruence product rule**

**LEMMA** $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$

**Proof** $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB – ab $

This congruence product rule is at the heart of many other similar product rules, for example Leibniz’s product rule for derivatives in calculus, e.g. see my post here.

1/4 = 4/16 = 4/7 = 8/14 = 8/5 = 16/10 = 16/1 = 16 = 7.

Note that in the first step I multiplied the numerator and denominator by 4 instead of 3. That is because 3 is not co-prime with 9.

Using Gauss Fraction Method: 1/4 = 2/8 = 2/(-1) = -2 = 7

It is true that x = -2, but if you want to make that -2 a positive number you should do this:

- x = -2
- -2 ≡ 7 (mod 9)

so 7 is the inverse.

- Does this property characterize a space as Hausdorff?
- Can one tell based on the moments of the random variable if it is continuos or not
- On the decomposition of stochastic matrices as convex combinations of zero-one matrices
- Is metric (Cauchy) completeness “outside the realm” of first order logic?
- Irreducible, finite Markov chains are positive recurrent
- Clarification about $\mathbb{R^2} \cong \mathbb{C}$
- If $M/N$ and $N$ are noetherian $R$-modules then so is $M$
- What is second Bartlett identity?
- Parametric Equations Problem
- Dimension of $\Bbb Q(e)$ over $\Bbb Q$?
- Prove the limit exists
- Some questions on complex determinants and flat connections on a $U(1)$ bundle
- $M \oplus M \simeq N \oplus N$ then $M \simeq N.$
- How is a group made up of simple groups?
- How to show that $f : \mathbb{R}^n → \mathbb{R}^n$, $f(x) = \frac{h(\Vert x \Vert)}{\Vert x \Vert} x$, is a diffeomorphism onto the open unit ball?