Modular Arithmetic Flashcards
What is a residue class?
The collection of all integers congruent to a modulo n. For example, the residue class of 0 modulo 3 contains all the integers that are exactly divisible by 3.
Why is every odd number congruent to 1(mod 2)?
Every odd number has remainder 2 after division by 1.
What is Fermat’s little theorem?
If p is prime and a is not a multiple of p, then:
a^p-1 = 1(mod p)
What is the Hardy-Ramanujan number and why is it special?
It is the number 1729, which is the smallest number that can be expressed as the sum of two cubes in two different ways.
1729 = 1^3 + 12^3 = 9^3 + 10^3
State the test for divisibility by 3.
If an integer is divisible by 3, then so is it’s digit sum.
State the test for divisibility by 9.
If an integer is divisible by 9, then so is it’s digit sum.
State the test for divisibility by 4.
If an integer is divisible by 4, then the number formed from the final two digits of the integer is also divisible by 4.
What are co-prime integers?
Two integers for which the highest common factor they share is 1.
If two integers a and n are co-prime, then there exists a multiplicative inverse of a modulo n.
What is a multiplicative inverse of a modulo n?
An integer v, such that av=1(mod n).
The solution set of a linear congruence ax=b(mod n) is given as…?
x=vb(mod n), where v is a multiplicative inverse of a modulo n.
If a linear congruence ax=b(mod n) has integers a and n that are not co-prime, when does it have solutions? State an equivalent linear congruence.
It has solutions when b is divisible by d, the highest common factor of he integers a and n.
a/d(x) = b/d(mod n/d)
What is the rule E for an affine cipher modulo 26?
E(x) = ax + b (mod 26)
Where a and b are integers, and a and 26 are co-prime.
What is the rule D for deciphering a message encoded by an affine cipher modulo 26 with rule E?
D(y) is the inverse function of the rule E(x).
D(y) = v(y-b)(mod 26)
Where v is any multiplicative inverse of (a) modulo 26.
