Begin2.DVI

10-17. Background material

Definition: (Congruence) Two integers I and J are said to

be congruent modulo L,(written I≡J(mod L)) if I−J=nL for

some integer n

This definition implies that two integers are congruent modulo Lif and only if

they have the same remainder when divided by L. Some examples are:

13 ≡1(mod 12 )

26 ≡2(mod 12 )

54 ≡6(mod 12 )

7 ≡1( mod 3 )

34 ≡1( mod 3 )

305 ≡2( mod 3 )

31 ≡2(mod 29 )

77 ≡19( mod 29 )

46 ≡17( mod 29 )

CRYPTOGRAMS (A writing in cipher.) The message, “HOW ARE YOU?”could

be written as a matrix of dimension 3 × 3 in the form

A=





H O W

A R E

Y O U



.

Associate with each letter of the alphabet an integer as in the following scheme:

A= 1

B= 2

C= 3

D= 4

E= 5

F= 6

G= 7

H= 8

I= 9

J= 10

K= 11

L= 12

M= 13

N= 14

O= 15

P= 16

Q= 17

R= 18

S= 19

T= 20

U= 21

V = 22

W= 23

X= 24

Y = 25

Z= 26

? = 27

Blank = 28

! = 29

Here 29 symbols are used as it is desirable to do modulo arithmetic in the modulo

29 system ( 29 being a prime number) and the blank stands for a blank character.

By replacing the letters in the above matrix A, by their number equivalents, there

results

A=





8 15 23

1 18 5

25 15 21



.

To disguise this message, the matrix A is multiplied by another matrix C, to

form the matrix B=AC. In this multiplication, modulo 29 arithmetic is used as it is

desired that only numbers between 1 and 29 are needed for our result. For example,

using the matrix

C=





1 1 0

0 1 − 1

1 −2 4



 with C−^1 =





2 − 4 − 1

−1 4 1

−1 3 1



