How to Solve Modular Equations in Mathematica?

[heartless]

Hello,
I'm not very experienced with mathematica, and I have some problems in making an equation like this,
Find x such that 11x = 1 (mod 360) and x < 360.
Any ideas on how to input this into mathematica?
Thanks,

 

[heartless]

or at least tell me how to find x?

 

[heartless]

actually x equals 131. It took me quite a few minutes to brute force it though (trial and error). I'm working out a formula now.

 

[Hurkyl]

AFAIK, you have to do the solving yourself. But at least you can still get Mathematica to do the computation...

The whole problem boils down to finding the modular inverse of 11, modulo 360. That is, the number a such that 11a = 1 (mod 360).

Mathematica might have a modular inverse function.

If not, the normal way to compute modular inverses is through the extended Euclidean algorithm for GCD's... Mathematica ought to have that!

This algorithm gives you the numbers u and v such that 11u + 360v = 1, so u is easily seen to be the inverse of 11 modulo 360. (Of course, this only works because GCD(11, 360) = 1)

If Mathematica doesn't have that, I think the easiest solution is to write a function that implements the extended Eucllidean algorithm.

But if you really don't want to, you could still manage something with modular exponentiation, since:

11^EulerPhi[360] = 1 (mod 360)

so you can spend a little bit of time figuring out the possibilities for things which 11a = 1 (mod 360).

(the Carmichael lambda function is better to use than the EulerPhi function, but I don't know if Mathematica has that)

 

[robert Ihnot]

There is a neat way to do this relying on the Chinese Remainder Theorem. We look at M, the total product and we divided by each Mi , the result we call individually Mi*. We must have all the M*s relatively prime to each other. So, while that may not be clear, we have 5x8x9=360, and the three factors 5,8,9 are relatively prime.

Then we solve X/Mi Modulo, 5, 8, and 9, giving us a series of Qi.

We have the equation X = Sum of Mi*(Qi). This gives the answer, which we reduce to lowest terms.

This requires good nomenclature to put it down right. But the proof is rather simple, since we have Mi*(Qi)==X Modulo Mi.

For instance in the case of 8x9(X/8x9 Mod 5) gives 8x9(11/72 Mod 5)=72(1/2 Mod 5)=72x3=216.

If you want to use a computer program, Pari has no problem with such things. Just use the Mod function: Mod(1/11,360) =Mod(131,360) in an augenblick!

In fact, it has no trouble with 13X==1 Mod 11!, Mod(1/13,11!)= Mod(36846277, 39916800)

 

[rad0786]

im sorry for my ignorance, but i havnt learned anything in Number Theory yet.

here goes...

What exactly is mod?

 

[VietDao29]

You can have a look at this page: Modulo to get some ideas about what modulo is.
We write:
$$a \equiv b (\mbox{mod } c)$$, that means when divided by c, a and b have the same remainder. :)