Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

RSA Laboratories

A.2 Modular arithmetic

Given integers a,b, and n with n > 0, we say that a and b are congruent modulo n if a-b is divisible by n, that is, if [(a-b)/( n)] is an integer. We write

a ºb (mod n)

if a and b are congruent modulo n>. Let a,b,c, and d be integers such that a ºc  (mod  n) and b ºd  (mod  n). It is not difficult to prove that

a+b º c+d (mod n) (1)

and

a b º c d (mod n). (2)

Given a fixed integer n > 0, called the modulus, we may form congruence classes of integers modulo n. Each congruence class is formally a set of the form

[a]: = a + n Z = { ¼, a-2n, a-n, a, a+n, a+2n, ¼}.

By (1) and (2), addition and multiplication of congruence classes is well-defined. More precisely, we define [a]+[b] = [a+b] and [a] ·[b] = [ab]. It is convenient to identify the element [a] with the smallest nonnegative number a¢ such that a º a¢ (mod  n) . This number a¢ will be denoted a  mod  n . For example, 13  mod  5 = 3. Let Zn denote the set of congruence classes modulo n. For example, Z5 = {0,1,2,3,4}.

The greatest common divisor (gcd) of two integers m and n is the greatest positive integer d such that d divides both m and n. For example, gcd(91,52) = 13. The Euclid algorithm states that if gcd(m,n) = d, then there are integers r and s such that mr + ns = d. In particular, the equation

mx º b (mod n) Û mx = b  (in Zn) (3)

has a solution x if and only if b is divisible by d.

Let Zn* be the set of integers (congruence classes modulo n) k Î {1, ¼, n-1} with the property that gcd(k,n) = 1. For example, Z12* = {1,5,7,11}.


Top of the page

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.