Math Is Fun Forum

user1234

Member

Registered: 2006-11-21

Posts: 8

modular arithmetic question!

hi! i am confused on how you would work out the following with modular arithmetic:

2^-1 mod 9

that is 2 to the power of -1 in mod 9. how would you work it out if the mod is not a prime?
and why does it make difference whether its prime or not?

thank you!

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: modular arithmetic question!

shoudn't it be in the form of  a=b (mod c) ???

---

Numbers are the essence of the Universe

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: modular arithmetic question!

That’s what I think it means – i.e. 1 divided by 2 equals 5 in modulo-9 terms.

The fact that 9 is not prime means that the integers modulo 9 do not form a field. Not every nonzero element has a multiplicative inverse modulo 9 – indeed, the two such elements are 3 and 6. There is no integer n such that 3n or 6n is congruent to 1 mod 9.

Last edited by JaneFairfax (2007-04-03 06:38:17)

meagain

Guest

Re: modular arithmetic question!

ok but how would u work out 5^-1 mod 9? is there a methodology of some sort for working out modular arithmethic if the modulus is not prime?
thanks!:)

meagain

Guest

Re: modular arithmetic question!

no actually u can, because 10/5 is 2! so the answer is 2. ok what about 4^-1 mod 9?
it doesnt work with that one?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: modular arithmetic question!

1 ≡ 28 mod 9 and 28 divided by 4 = 7, so 1 divided by 4 equals 7 in modulo 9.

The list:

1 divided by 1 ≡ 1 mod 9
1 divided by 2 ≡ 5 mod 9
1 divided by 3 – no solution in mod 9
1 divided by 4 ≡ 7 mod 9
1 divided by 5 ≡ 2 mod 9
1 divided by 6 – no solution in mod 9
1 divided by 7 ≡ 4 mod 9
1 divided by 8 ≡ 8 mod 9

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: modular arithmetic question!

When ever answering questions in number theory, it is just about always best to stay away from division, as division is not a binary operation on the integers.  For example, when we say that m divides n, we don't say:

n / m = k, where k is an integer.

Instead, we say:

n = mk, where k is an integer.

So always try as best as you can to avoid division.  It can get you into a lot of trouble.

To comput the inverse of a number, one simply must compute phi(n).

A special property of phi(n) is that:

This only holds when gcd(a, n) = 1.  So then:

So for your two numbers:

Note that this won't work for 3^6, as

And it won't for 6 because:

So you must make sure that gcd(a, n) = 1 first.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."