Math Is Fun Forum

ShivamS

Member

Registered: 2011-02-07

Posts: 3,648

Re: Any better method than guessing?

Sorry, I have never heard of that notation.

zetafunc.

Guest

Re: Any better method than guessing?

Sorry, I have never heard of that notation.

[a] is also used, if the modulus has been given.

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Re: Any better method than guessing?

Hi zetafunc.,

How did you compute the modular inverse of 9?

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Fruityloop

Member

Registered: 2009-05-18

Posts: 143

Re: Any better method than guessing?

We have a linear Diophantine equation.
9y - 17 = 11x
y-(17/9) = x + (2x/9)
y-x-1 = (8+2x)/9
Because x and y are integers so is (8+2x)/9.
(8+2x)/9=z
8+2x = 9z
4+x=4z+(z/2)
4+x-4z=(z/2)
z=2w
we have
8+2x=18w
so we have
x=9w - 4
y=11w - 3
So we have 2 solutions x=-4 and y=-3 also x=5 and y=8
To get the other number we subtract y from 11.
so we have 83 as one solution and -38 as another solution also -83 is another solution.

Last edited by Fruityloop (2014-04-08 16:58:22)

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Re: Any better method than guessing?

x=9w - 4
y=11w - 3

How do you solve that?

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

zetafunc.

Guest

Re: Any better method than guessing?

Hi zetafunc.,

How did you compute the modular inverse of 9?

What we want to do is find an a such that

.

From here you could use trial and error and try all possible values of a until you find one that satisfies the above relation. This works well for a smaller modulo, but for larger ones, we need a better technique. A more efficient way of finding the inverse for larger numbers is to use the Euclidean algorithm.

If

, then p does not divide a, and hence a and p are coprime. By the h,k-lemma, there exist integers h,k such that ph + ak = 1. Then,

in

, and hence

. We can find h,k via the Euclidean algorithm. In our example, we wish to compute gcd(9, 11). (This is trivial but we're not interested in the final result.)

11 = (1 × 9) + 2
9 = (4 × 2) + 1

Re-arranging, we see that 1 = (5 × 9) + (-4 × 11), and the modular inverse of 9 is 5.

ShivamS

Member

Registered: 2011-02-07

Posts: 3,648

Re: Any better method than guessing?

I have heard different countries use different notation. For example, here in the US, when considering an n-dimensional space, mathematicians write it as R^n,. At Cambridge, they write it as d-dimensional space denoted with R^d.