Prove or disprove: A natural number n ≥ 2 is a prime if for every integer b between 1 and n − 1.
Suppose not. Suppose that there is a natural number , which is a not prime but for all .
Because n is not a prime, there must be integers r and s both greater than 1 such that . Because , it follows that by our assumption. By the definition of congruence modulo n, there exists k such that . Thus, and . But this is impossible since . Thus, our supposition is false, and any natural number such that for all is a prime. Q.E.D.
In my failed attempts to prove this statement, I accidentally proved the following two theorems. Since the results are pretty nice, I’ll include it here.
Cancellation Law in Modular Arithmetic
If k, r, and s are integers, n is a prime, and k is not divisible by n and , then .
Proof: Let k, r, s, and n be integers such that and . By the definition of congruence modulo n, or that . By Euclid’s lemma (for all integers a, b, and c, if and , then ), since . Thus by the definition of congruence modulo n, . Q.E.D.
Fermat’s Little Theorem
If a is an integer and b is a prime, then .
Proof: Let a be any integer and b be any prime. Then a ≠ 0 because otherwise .
Consider a set . Suppose for some integers k and m such that 1 ≤ k < m ≤ b. Since , by the cancellation law. By the definition of congruence modulo b, . But this is impossible since . Thus, every element in P belongs to a distinct equivalence class defined by congruence modulo b.
Now let us define a function F from P to a defined as . Then F is one-to-one because every element in P belongs to a distinct equivalence class defined by congruence modulo b, and Q is simply a set of the class representatives. Furthermore, F is onto because because F is one-to-one and P and Q have the same cardinality.
Thus, by the commutative law of modular arithmetic. Because b is a prime, . Applying the cancellation law yields: as desired. Q.E.D.
Epp., S. S. (2004). Discrete Mathematics with Applications. Cengage Learning.