Understanding some elementary number theory is necessary if we are to understand cryptosystems and how quantum computers can be used to break them. In this appendix we review some basic facts about number theory.
Fundamentals
Let's start off by agreeing about a few conventions for nomenclature and notation. The set of integers is the set {…, −2, −1, 0, 1, 2, …}, denoted Z. We may occasionally refer to the natural numbers, meaning non-negative integers, but more often we'll say non-negative integer or positive integer, in order to make the distinction between the case when zero is included, and when zero is not included.
Suppose n is an integer. An integer d divides n (written d|n) if there exists an integer k such that n = dk. We say in this case that d is a factor or divisor of n. Notice that 1 and n are always factors of n. When d does not divide (is not a factor of) n we write d∤n. For example, 3|6 and 3|18, but 3∤|5 and 3∤7.
Exercise A4.1: (Transitivity) Show that if a|b and b|c then a|c.
Exercise A4.2: Show that if d|a and d|b then d also divides linear combinations of a and b, ax + by, where x and y are integers.
Exercise A4.3: Suppose a and b are positive integers. Show that if a|b then a ≤ b. Conclude that if a|b and b|a then a = b.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.