Linear Diophantine Equations and Linear Congruences - Introduction to Cryptography with Java Applets - page 94

b. 44 = 7 6 + 2, and

c. 17 = 5 4 + 3.

Java Algorithm. Since we now have the concept of the least nonnegative residue, we
should write a Java method (in the BigIntegerMath class) to compute it. The BigInteger
class provides a mod() method, but the Java documentation says it can return a negative
remainder if the dividend is negative. We correct this by just adding the value of the mod-
ulus to the residue if it is negative. Also, recall that we do not allow negative moduli.

//Computes the least nonnegative residue of b mod m, where m>0.
public static BigInteger lnr(BigInteger b, BigInteger m) {
if (m.compareTo(ZERO)<=0)
throw new IllegalArgumentException(“Modulus must be positive.”);
BigInteger answer=b.mod(m);
return (answer.compareTo(ZERO)<0)?answer.add(m):answer;

}

We would like to be able to form some rules of algebra for congruences. Many rules that
hold for equations also hold for congruences.

PROPOSITION 19. Let a , b , and c be integers, and let m be a positive integer. Suppose

a b (mod m ). Then
a.

a + c b + c (mod m )

b. a c b c (mod m )

c. ac bc (mod m ).

Proof.

a. We prove the first here. We have a b (mod m ), so m |( a b ). But a b = ( a + c )

( b + c ), and this is divisible by m , hence a + c b + c (mod m ).

b. (For you to prove.)

c. (For you to prove.)

We can do even better than the properties of proposition 19 when dealing with congru-
ences. That is, we do not have to add, subtract, or multiply by the same element on both sides
of a congruence to preserve it, but only by elements that are congruent modulo m . These
properties are easily established, and are left to you to prove.

PROPOSITION 20. Let a , b , c , and d be integers, and let m be a positive integer. Sup-
pose a b (mod m ), and c d (mod m ). Then
a. a + c b + d (mod m )

b. a c b d (mod m )

c. ac bd (mod m ).