Hello,

How can I compute:

mod ?

Regards.

Printable View

- Jun 20th 2010, 12:05 PMMigotek84Modular arithmetic
Hello,

How can I compute:

mod ?

Regards. - Jun 20th 2010, 12:09 PMundefined
The two ways I know of are: (1) Extended Euclidean algorithm (2) Modular exponentiation. See here for some discussion. If you'd like an example, just ask, and I or someone else will provide one.

- Jun 20th 2010, 02:14 PMtonio
- Jun 20th 2010, 10:43 PMsimplependulum
There is a general method to find the inverse , you know , it is Euclidean Algorithm , but i promise once you have practised a lot , it would be very easy for you to solve , without Euclidian Algorithm .

- Jun 28th 2010, 06:53 AMBacterius
Also, without going too deeply in the number theoretical realm, if you know the Euler totient of the modulus, you can efficiently compute :

In order to do this you use the modular exponentiation (square and multiply) algorithm, and is the Euler totient of 23 (which incidentally equals 22). - Jun 29th 2010, 05:06 PMSoroban
Hello, Migotek84!

Here's aprimitive method . . .*very*

Quote:

Compute: .

Let: .

Multiply by 17: .

Then: .

.[1]

Since is an integer, is a multiple of 17.

. .

.[2]

Since is an integer, is a multiple of 6.

. .

.[3]

Since is an integer, is a multiple of 5.

. . The first time this happens is when .

Substitute into [3]: .

Substitute into [2]: .

Substitute into [1]: .

Therefore: .

- Jun 29th 2010, 08:51 PMBacterius
Hey Soroban,

I remember having seen this method on some Wikipedia article, when I first discovered modular arithmetic (nearly a year ago). I really liked it, if I recall correctly this is the Euclidian Algorithm backwards, right ? (Worried)