Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#26 2014-04-08 13:59:22

ShivamS
Member
Registered: 2011-02-07
Posts: 3,519

Re: Any better method than guessing?

Sorry, I have never heard of that notation.

Offline

#27 2014-04-08 14:10:23

zetafunc.
Guest

Re: Any better method than guessing?

ShivamS wrote:

Sorry, I have never heard of that notation.

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

#28 2014-04-08 15:24:36

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
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'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#29 2014-04-08 16:57:53

Fruityloop
Member
Registered: 2009-05-18
Posts: 120

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)


The eclipses from Algol (an eclipsing binary star) 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

#30 2014-04-08 17:47:58

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 15,916
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'
'Humanity is still kept intact. It remains within.' -Alokananda

Offline

#31 2014-04-08 21:25:56

zetafunc.
Guest

Re: Any better method than guessing?

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.

#32 2014-04-09 00:49:40

ShivamS
Member
Registered: 2011-02-07
Posts: 3,519

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.

Offline

Board footer

Powered by FluxBB