Question

Number theory:
As a practical matter, is there a simple way to determine the inverse of a number mod n?

Answer 1

For example, if I have 504s congruent to 14 (mod 35), is there an easy way to find \[504^{-1}(14) \mod35\]

Answer 2

you want to solve \[504x\equiv 14\pmod{35}\]

right ?

Answer 3

Yes, as part of a Chinese Remainder Theorem problem

Answer 4

reduce 504 first

Answer 5

Would you also need to reduce the 35 at the same time?

Answer 6

Oh, their GCD is 7

Answer 7

504 =35*14 + 14

Answer 8

so \(504 \equiv 14 \pmod{35}\)

Answer 9

If we do that, don't we need to divide 35 by GCD(35, 504)?

Answer 10

you want to solve \[504x\equiv 14\pmod{35}\]

reduces to
\[14x\equiv 14\pmod{35}\]

Answer 11

we are not dividing anything yet
we are just using the fact that \(504\equiv 14\)

Answer 12

I think I'm having trouble with the difference between the idea of reducing versus dividing

Answer 13

lets divide 14 through out
you will see the difference then i hope :)

Answer 14

So 14x is congruent to 14 mod(35) and we have x=1?

Answer 15

\[14x\equiv 14\pmod{35}\]

dividing 14 though out gives you


\[\dfrac{14x}{14}\equiv \dfrac{14}{14}\pmod{\dfrac{35}{\gcd(35,14)}}\]

Answer 16

\[x\equiv 1 \pmod{5}\]

Answer 17

Ah, I see the difference now. Thanks for your help!

Answer 18

we have been using two properties of congruences

Answer 19

\(a\equiv b\pmod{n}\) and \(b\equiv c\pmod{n} \implies a\equiv c\pmod{n}\)

that allows you to replace 504 by 14

Answer 20

One's using the transitive property, and the other is using an inverse property?

Answer 21

yes :)
in the end you have used
\[ac \equiv bc\pmod{n} \implies a\equiv b\pmod{\frac{n}{\gcd(c,n)}}\]

Answer 22

:)

Answer 23

Thank you for your help - this clarifies things a lot!

Answer 24

you must be knowing solving a congruence is same as solving the diophantine eqn :

\[ax \equiv b \pmod{n}\]

is equivalent to solving

\[ax -ny = b\]

so you can use all the methods that work for diophantine equations to solve ur congruence

Answer 25

you're welcome :)

Answer 26

Huh, I haven't seen it put in terms of a Diophantine Equation like this

Answer 27

\(ax\equiv b\pmod{n}\)

means

\(ax = ny + b\) for some integer \(y\)

rearrange to get the standard linear diophantine eqn form

Answer 28

so your original problem is same as solving the diophantine eqn

\(504x-35y = 14\)

Answer 29

it is now a regular equation so we can divide 7 through out

\(72x-5y = 2\)

Answer 30

this is actually the standard method for finding inverse when no other simplification is possible

this method works always

Answer 31

That's much easier to think about. I hadn't really been thinking of these things as Diophantine equations or linear combinations of variables, and I suppose I should.

Answer 32

you could also use chinese remainder thm

Answer 33

you said you want to solve it using chinese remainder thm , so.. lets work it using chinese remainder thm quick maybe

Answer 34

\(504x\equiv 14\pmod{35} \)

split it into two congruences

\(504x\equiv 14\pmod{5} \)
\(504x\equiv 14\pmod{7} \)

work each congruence separately and combine them using chinese remainder thm

Answer 35

chinese remainder thm helps here because mod 5 and mod 7 are simpler to work compared to mod 35

Answer 36

In the first equation, we have 4x congruent to 4 (mod5), and so x = 1
In the second equation, could use any integer, so we could take x = 0 (?)

Answer 37

Oh, we want x to be the same in each case, so x=1

Answer 38

Oh yes we can drop second congruence because x could be any integer

Answer 39

we're done yeah
no need to apply chinese remainder thm

Answer 40

So suppose it didn't work out that way, how would the Chinese Remainder Theorem help?

Answer 41

Say, if we used 505 instead of 504?

Answer 42

lets cookup an example

Answer 43

ohk lets use 505

Answer 44

it has no inverse because gcd(505, 35) does not divide 14

Answer 45

pick some other good number

Answer 46

How about 25 congruent to 1 (mod 6)

Answer 47

25x*

Answer 48

knw what, there is nothing to solve there
25 = 1 mod 6

:P

Answer 49

so 25x = 1 mod 6
can be solved trivially by reducing to x = 1 mod 6

Answer 50

Right, but just as a demonstration of the Chinese Remainder Theorem when you use 2 and 3

Answer 51

Ahh okay I see what you mean

Answer 52

\(25x \equiv 1 \pmod{6}\)

split into two

\(25x \equiv 1 \pmod{2}\)
\(25x \equiv 1 \pmod{3}\)

Answer 53

*Sorry, brb

Answer 54

solving each gives
\(x\equiv 1\pmod{2}\)
\(x\equiv 1\pmod{3}\)

by chinese remainder thm the solution would be below expression mod 6 :
\[1\times 3 \times 3^{-1}\pmod 2 + 1\times 2\times 2^{-1}\pmod{3}\]

right ?

Answer 55

I'm with you

Answer 56

**\[1\times 3 \times [3^{-1}\pmod 2 ]+ 1\times 2\times [2^{-1}\pmod{3}]\]

Answer 57

inverse of 3 in mod2 is 1
and inverse of 2 in mod 3 is 2

plug them

Answer 58

lets work a not so simple congruence after this

Answer 59

1(3)(1)+1(2)(2) congruent to a mod 6
7 congruent to a mod 6
And we get 1 mod 6

Answer 60

yes that was easy, try solving this using chinese remainder thm
\[17x\equiv 9 \pmod{276}\]

Answer 61

17x congruent to 9 mod 12
17x congruent to 9 mod 23

Answer 62

yes

Answer 63

I suppose we could further split these up to
17x congruent to 9 mod 3
17x congruent to 9 mod 4

2x congruent to 0 mod 3, x=0
x congruent to 1 mod 4, x=1

Answer 64

Oh, yeah, I got stuck with the 5x congruent to 9 mod 12

Answer 65

looks good!

Answer 66

```
I suppose we could further split these up to
17x congruent to 9 mod 3
17x congruent to 9 mod 4

2x congruent to 0 mod 3, x=0
x congruent to 1 mod 4, x=1
```

use chinese remainder thm to cookup solution for 17x congruent to 9 mod 12

Answer 67

So we have 0 + 1(4)(1) [mod 12]?

Answer 68

Lol, 4 mod 12

Answer 69

im getting 9 mod 12

Answer 70

By I i mean wolfram :)

Answer 71

whats the inverse of 3 in mod4 ?

Answer 72

3

Answer 73

x = 0 mod 3
x = 1 mod 4

chinese remainder thm gives

0 + 1*3*3 mod 12

Answer 74

OH, haha, I was looking at the wrong modulus

Answer 75

\[0 + 1\times 3\times [3^{-1}\pmod{4}]\]

Answer 76

Yeah, I'm with you. Stupid mistake.

Answer 77

So now there's the part with the 17x congruent to 9 mod 23

Answer 78

17x congruent to 9 mod 12 : solution ` x = 9 mod 12`
17x congruent to 9 mod 23

Answer 79

lets work second congruence quick

Answer 80

17x congruent to 9 mod 23

reduces to

-6x congruent to 9 mod 23

yes ?

Answer 81

Yes

Answer 82

divide 3 through out :

-2x congruent to 3 mod 23

Answer 83

Ah, clever

Answer 84

we can eyeball now
x = 10

Answer 85

Isn't it -10?

Answer 86

17x congruent to 9 mod 12 : solution `x = 9 mod 12`
17x congruent to 9 mod 23 : solution `x = 10 mod 23`

Answer 87

-2x congruent to 3 mod 23

-2(10) = 3 mod 23

-20 = 3 mod 23

which is true right

Answer 88

*head bonk* Sorry

Answer 89

K, good now

Answer 90

below is the most useful definition of congruence :
\(a \equiv b \pmod{n}\) means \(a -b\) is divisible by \(n\)

Answer 91

you have solutions
work chinese remainder thm again and call it a day !

Answer 92

So we still need to work the inverses for 9 mod 12 and 10 mod 23, right?

Answer 93

basically we are doing this :

we have 17x congruent to 9 mod 276 to solve

we solved below baby congruences and hoping to stitch the final solution using chinese remainder theorem :
17x congruent to 9 mod 12 : solution `x = 9 mod 12`
17x congruent to 9 mod 23 : solution `x = 10 mod 23`

Answer 94

Right

Answer 95

yes

Answer 96

repeat the same story :)

Answer 97

just the numbers are different now

Answer 98

method is same