# Introduction to Modular Arithmetic and Euclidean Algorithm

Page 1 of 1

## 0 Replies - 36033 Views - Last Post: 28 June 2011 - 05:46 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=237418&amp;s=bc2725e27089a76d2a6e761980b49568&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12149
• Posts: 45,170
• Joined: 27-December 08

# Introduction to Modular Arithmetic and Euclidean Algorithm

Posted 28 June 2011 - 05:46 PM

This tutorial will cover basic number theory, including modular arithmetic and the Euclidean algorithm.

Modular Arithmetic
Modular arithmetic is based on the modulus operator, which returns the remainder of a/b. So 5 (mod 3) is equivalent to 2. It also ensures that no number is greater than the modulus.

Negative numbers are also handled the same way. However, rather than going forward, start at the modulus and work backwards. So -4 (mod 3) is equivalent to 2. Start at 2 (since 3 is the base, subtract 1 from 3 and start there), then work down to 0. Now loop around to the base (3). Repeat until having iterated backwards 4 times.

Modular arithmetic also utilizes inverses. A modular inverse is defined such that if ab (mod x) is equivalent to 1, then a and b are modular inverses of each other for base x. For example, 3 and 2 are modular inverses for base 5, because 3(2) (mod 5) = 6 (mod 5) = 1.

It is also possible to quickly reduce exponential expressions due to the cyclic nature of modular arithmetic. Given an expression an (mod x), it can quickly be simplified as [a (mod x)]n (mod x) (mod x). In other words, if the exponent is greater than the modular base, reduce it mod x, and if the exponential base is greater than the modular base, reduce a (mod x). For example, 1322 (mod 10) can easily be simplified as 32 (mod 10), which is much more manageable to deal with.

Euclidean Algorithm
The Euclidean Algorithm is used to find the greatest common factor of two numbers. It works by repeatedly subtracting the smaller of the two numbers until they are the same. Or in pseudo-code:
```euclideanAlgorithm(a, b)
while a != b
while a > b
a -= b
while b > a
b -= a
return a

```

To go with this algorithm is the formula ax + by = euclideanAlgorithm(a,b). This leads into solving for modular inverses. Let's start with an example: gcd(24, 13) = 1. So working through the algorithm:
24 - 13 = 11
13 - 11 = 2
11 - 2(5) = 1

The next step is to work backwards, substituting the previous equation into the one currently being worked with. So given the form ax + by = gcd(24, 13), the ax and by terms may change, but the result will always remain 1. So
11(1) - 2(5) = 1

The previous equation is 13 - 11 = 2. Since there is a 2 in the last equation, (13-11) is substituted in its place:
11(1) - (13-11)(5) = 1

Now distribute the 5 to get a new equation:
11(1) + 5(11) - 13(5) = 1
11(6) - 13(5) = 1

In the first equation, 11 is on the right hand side, (24-13) will be substituted into the 11 term in 11(6) - 13(5). Notice how the 11 disappears, leaving the equation in the form ax + by = gcd(a,b).
(24-13)(6) - 13(5) = 1

The final equation: 24(6) - 13(11) = 1.

This makes it very easy to find the modular inverses of 13 and 24 with respect to each other. So 24(6) (mod 13) is equivalent to 1, and 13(-11) (mod 24) is equivalent to 1. Remember that -11 (mod 24) is equivalent to 13. Thus, 6 and 13 are the respective modular inverses of 24 (mod 13) and 13 (mod 24). So when trying to find the modular inverse of a number, simply set up the formula ax + by = gcd(a, b), where a is the number to find the modular inverse for and b is the modular base.

Is This A Good Question/Topic? 4

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }