You are not logged in.

- Topics: Active | Unanswered

**ShivamS****Member**- Registered: 2011-02-07
- Posts: 3,648

Sorry, I have never heard of that notation.

Offline

**zetafunc.****Guest**

ShivamS wrote:

Sorry, I have never heard of that notation.

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

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.

Offline

**Fruityloop****Member**- Registered: 2009-05-18
- Posts: 134

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)*

**The eclipses from Algol come further apart in time when the Earth is moving away from Algol and closer together in time when the Earth is moving towards Algol, thereby proving that the speed of light is variable and that Einstein's Special Theory of Relativity is wrong.**

Offline

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.

Offline

**zetafunc.****Guest**

Agnishom wrote:

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

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.

Offline