Math Is Fun Forum

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

You are not logged in.

#1 2007-04-03 04:32:39

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! smile

Offline

#2 2007-04-03 05:41:45

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

Offline

#3 2007-04-03 06:33:04

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)

Offline

#4 2007-04-04 04:09:30

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!:)

#5 2007-04-04 04:11:39

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?

#6 2007-04-04 06:35:58

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

Offline

#7 2007-04-04 06:40:27

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..."

Offline

Board footer

Powered by FluxBB