| Home / lib / tmp / | ||
Stein W. Elementary number theory and elliptic curves (web draft, Sept. 2004)(182s).pdf |
|
Size 1.2Mb Date Jan 10, 2006 |
1.2.4 Primes of the Form ax + b
Next we turn to primes of the form ax + b, where a and b are fixed integers with a > 1 and x varies over the natural numbers N. We assume that gcd(a, b) = 1, because otherwise there is no hope that ax + b is prime infinitely often. For example, 2x + 2 = 2(x + 1) is only prime if x = 0, and is not prime for any other x ∈ N. Prop osition 1.2.4. There are infinitely many primes of the form 4x − 1. Why might this be true? We list numbers of the form 4x − 1 and underline those that are prime: 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, . . . It is plausible that underlined numbers would continue to appear indefinitely. Proof. Suppose p1 , p2 , . . . , pn are distinct primes of the form 4x − 1. Consider the number N = 4p1 p2 · · · pn − 1. Then pi N for any i. Moreover, not every prime p | N is of the form 4x + 1; if they all were, then N would be of the form 4x + 1. Thus there is a p | N that is of the form 4x − 1. Since p = pi for any i, we have found a new prime of the form 4x − 1. We can repeat this process indefinitely, so the set of primes of the form 4x − 1 cannot be finite. Note that this proof does not work if 4x − 1 is replaced by 4x + 1, since a product of primes of the form 4x − 1 can be of the form 4x + 1. N = 4 · 3 · 7 − 1 = 83...
1.3 Exercises
1.1 Compute the greatest common divisor gcd(455, 1235) by hand. 1.2 Use the Sieve of Eratosthenes to make a list of all primes up to 100. 1.3 Prove that there are infinitely many primes of the form 6x − 1. 1.4 Use Theorem 1.2.8 to deduce that lim
x→∞...
has a unique solution a ∈ {1, 2, . . . , p − 1}. If a = a , then a2 ≡ 1 (mod p), so p | a2 − 1 = (a − 1)(a + 1), so p | (a − 1) or p | (a + 1), so a ∈ {1, p − 1}. We can thus pair off the elements of {2, 3, . . . , p − 2}, each with their inverse. Thus 2 · 3 · · · · · (p − 2) ≡ 1 (mod p). Multiplying both sides by p − 1 proves that (p − 1)! ≡ −1 (mod p). Next we assume that (p − 1)! ≡ −1 (mod p) and prove that p must be prime. Suppose not, so that p ≥ 4 is a composite number. Let be a prime divisor of p. Then < p, so | (p − 1)!. Also, by assumption, | p | ((p − 1)! + 1). This is a contradiction, because a prime can not divide a number a and also divide a + 1, since it would then have to divide (a + 1) − a = 1. Example 2.1.14. We illustrate the key step in the above proof in the case p = 17. We have 2 · 3 · · · 15 = (2 · 9) · (3 · 6) · (4 · 13) · (5 · 7) · (8 · 15) · (10 · 12) · (14 · 11) ≡ 1 (mod 17),...
Algorithm 2.3.7 (Compute Power). Let a and n be integers and m a nonnegative integer. This algorithm computes am modulo n. 1. [Write in Binary] Write m in binary using Algorithm 2.3.6, so am = ε i a2 (mod n). i =1
2 3 2...
2.21 Prove that for any positive integer n the fraction (12n + 1)/(30n + 2) is in reduced form. 2.22 Suppose a and b are positive integers. (a) Prove that gcd(2a − 1, 2b − 1) = 2gcd(a,b) − 1....
3.2.2 Encoding a Phrase in a Number
In order to use the RSA cryptosystem to encrypt messages, it is necessary to encode them as a sequence of numbers of size less than n = pq . We now describe a simple way to do this. For an implementation of a slightly more general encoding that includes extra randomness so that plain text encodes differently each time, see Section 7.3.2. Suppose s is a sequence of capital letters and spaces, and that s does not begin with a space. We encode s as a number in base 27 as follows: a single space corresponds to 0, the letter A to 1, B to 2, . . ., Z to 26. Thus “RUN NIKITA” is a number written in base 27: RUN NIKITA ↔ 279 · 18 + 278 · 21 + 277 · 14 + 276 · 0 + 275 · 14 + 274 · 9 + 273 · 11 + 272 · 9 + 27 · 20 + 1 = 143338425831991 (in decimal)....
If 27k ≤ n, then any sequence of k letters can be encoded as above using a positive integer ≤ n. Thus if we use can encrypt integers of size at most n, then we must break our message up into blocks of size at most log27 (n)....
whose roots are p and q . These roots can be found using the quadratic formula. Example 3.3.1. The number n = pq = 31615577110997599711 is a product of two primes, and ϕ(n) = 31615577098574867424. We have f = x2 − (n + 1 − ϕ(n))x + n = x2 − 12422732288x + 31615577110997599711...
Theorem 4.1.5 (Gauss’s Quadratic Recipro city Law). Suppose p and q are distinct odd primes. Then p= q. p−1 q −1 (−1) 2 · 2 q p Also − 1 p = (−1)
(p−1)/2...
Remark 5.1.6. Exprep sed in teirms of matrices, the p ropositiion asserts that s p n pn−1 n pn−2 the determinant of qn qn−1 s (−1)n−1 , and of qn qn−2 s (−1)n an ....
Example 5.2.3. Suppose x = e = 2.71828182 . . .. Using the continued fraction procedure, we find that a0 , a1 , a2 , . . . = 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, . . . For example, a0 = 2 is the floor of 2. Subtracting 2 and inverting, we obtain 1/0.718 . . . = 1.3922 . . ., so a1 = 1. Subtracting 1 and inverting yields 1/0.3922 . . . = 2.5496 . . ., so a2 = 2. We will prove in Section 5.3 that the continued fraction of e obeys a simple pattern. The 5th partial convergent of the continued fraction of e is [a0 , a1 , a2 , a3 , a4 , a5 ] = 87 = 2.71875, 32...
Similarly, the first statement is true for n if it is true for n − 1. Theorem 5.2.5 (Continued Fraction Limit). Let a0 , a1 , . . . be a sequence of integers such that an > 0 for al l n ≥ 1, and for each n ≥ 0, set cn = [a0 , a1 , . . . an ]. Then lim cn exists.
n→∞...
5.3.1 Preliminaries
First, we write the continued fraction of e in a slightly different form. Instead of [2, 1, 2, 1, 1, 4, . . .], we can start the sequence of coefficients [1, 0, 1, 1, 2, 1, 1, 4, . . .] to make the pattern the same throughout. (Everywhere else in this chapter we assume that the partial quotients an for n ≥ 1 are positive, but...
5.6 Sums of Two Squares
In this section we apply continued fractions to prove the following theorem. Theorem 5.6.1. A positive integer n is a sum of two squares if and only if al l prime factors of p | n such that p ≡ 3 (mod 4) have even exponent in the prime factorization of n....
Algorithm 6.2.2 (Least Common Multiple of First B Integers). Given a positive integer B , this algorithm computes the least common multiple of the positive integers up to B . 1. [Sieve] Using the Sieve of Eratosthenes (Algorithm 1.2.3), compute a list P of all primes p ≤ B . p 2. [Multiply] Compute and output the product ∈P logp (B ) . ordp (m) = max({ordp (n) : 1 ≤ n ≤ B }) = ordp (pr ), where pr is the largest power of p that satisfies pr ≤ B . Since pr ≤ B < pr+1 , we have r = logp (B ) . We implement Algorithm 6.2.2 in Section 7.6.2....
| © 2007 eKnigu | ||