Math 124: Final Examination Solutions

William Stein

Math 124 Harvard University Fall 2001

1. First proof (using induction): The statement is true when n = 1, since gcd(1, 1) = 1. Now assume that n ≥ 2 is an integer such that gcd(F_{n−1}, F_{n}) = 1. If there is a prime p such that

p | gcd(F_{n}, F_{n+1}) = gcd(F_{n}, F_{n} + F_{n−1}),

then p | F_{n} and p | F_{n} + F_{n−1}, so p | F_{n−1} and p | F_{n}, hence p | gcd(F_{n−1}, F_{n}) which contradicts our inductive assumption. Thus no such prime p exists, and gcd(F_{n}, F_{n+1}) = 1.

Second proof (using continued fractions): Consider the periodic continued fraction [1, 1, 1, ...]. The nth convergent to this continued fraction is p_{n}/q_{n}, where p_{n} and q_{n} are defined by the recurrence p_{n} = p_{n−1} + p_{n−2}, q_{n} = q_{n−1} + q_{n−2}, and p_{−1} = p_{0} = 1, q_{−1} = 0, q_{0} = 1. As observed in Lecture 17, gcd(p_{n}, q_{n}) = 1. Now just notice that p_{n} = F_{n+2} and q_{n} = F_{n+1}.

2. We do part (ii), which implies part (i). Let T be the set of elements in (ℤ/nℤ)^{∗} of order dividing 2, and let S be the complement of T in (ℤ/nℤ)^{∗}, so

f(n) = ∏_{x∈S} x · ∏_{x∈T} x.

If x ∈ S then x^{−1} also lies in S and x^{−1} ≠ x, so ∏_{x∈S} x = 1, and f(n) = ∏_{x∈T} x, where T is the subgroup of elements of order dividing 2. Using the Chinese Remainder Theorem, write

(ℤ/nℤ)^{∗} ≅ (ℤ/p_{1}^{n_{1}}ℤ)^{∗} × ⋯ (ℤ/p_{r}^{n_{r}}ℤ)^{∗},

where n = ∏ p_{i}^{n_{i}} is the prime factorization of n. Since each p_{i} is odd, problem 4 of this exam implies that (ℤ/p_{i}^{n_{i}}ℤ)^{∗} is cyclic, so −1 is the only element it contains of order 2.

Thus the group T is isomorphic to the 𝔽 = (ℤ/2ℤ)-vector space 𝔽^{r}, where again r is the number of prime factors of n. By a careful induction we see that ∑_{a∈𝔽^{r}} ≠ 0 if and only if r = 1. To see this, check the cases r = 0, 1, 2 directly. For r ≥ 3, write 𝔽^{r} as a union of two (r − 1)-dimensional hyperplanes, the elements of each of which sum to 0, by the inductive hypothesis. Thus

f(n) = \begin{cases}−1, & when n ≠ 1 is a prime power \\ 1, & otherwise \end{cases}

For fun, here is a PARI program that compute f(n) directly, so you can verify computationally that the above result is plausible:

f(n)=local(s);s=1;for(x=1,n,if(gcd(x,n)==1,s=(s*x)%n));return(s);

3. (i) m^{e} = 267882027458254785570095246784538 (ii) The decryption key is the inverse of e modulo φ(n), which is

d = 208830632607306431636724371446103.

(iii) 2002.

4. First note, as observed in Lecture 6, that the group G = (ℤ/p^{n}ℤ)^{∗} has order

φ(p^{n}) = p^{n} − p^{n−1} = (p − 1)p^{n−1}.

We will prove that G is cyclic by proving that G contains an element of order (p − 1)p^{n−1}, and we’ll do this by showing that G contains an element of order p − 1 and one of order p^{n−1}.

In Lecture 11, we proved that the group (ℤ/pℤ)^{∗} of order p − 1 is cyclic, so since the homomorphism (ℤ/p^{n}ℤ)^{∗} → (ℤ/pℤ)^{∗} is surjective, there is an x ∈ (ℤ/p^{n}ℤ)^{∗} of order a multiple of p − 1. Then a = x^{p^{n−1}} has order p − 1. Next, letting b = 1 + p, the binomial theorem implies that

b^{p^{n−2}} = 1 + \binom{p^{n−2}}{1}p + \binom{p^{n−2}}{2}p^{2} + ⋯

= 1 + p^{n−1} + \frac{p^{n−2}(p^{n−2} − 1)}{2}p^{2} + ⋯,

so, since p ≠ 2, we have b^{p^{n−2}} ≢ 1 (mod p^{n}). (This argument fails when p = 2; e.g., if p = 2 and n = 3, then the right-most binomial coefficient is not divisible by p^{3}.) Since b^{p^{n−1}} ≡ 1 (mod p^{n}), we see that b has order p^{n−1}. Thus a · b has order lcm(p − 1, p^{n−1}) = φ(p^{n}), which proves that (ℤ/p^{n}ℤ)^{∗} is cyclic.

[If you’re worried about that binomial expansion, the following remark by “A. Student” might prove helpful: For i > 1 we have p^{n−i}|\binom{p^{n}}{i}, because \binom{p^{n}}{i} = p^{n} ·(p^{n} −1) ⋯ (p^{n} −i+1)/(i!) and the power of p in the factorization of i! satisfies i/p + i/p^{2} + ⋯ ≤ i(1/(p − 1)) < i.]

5. (i) Let α = [0, \overline{1, 4}]. Then

α = \frac{1}{1 + \frac{1}{4+α}} ,

so α = (4 + α)/(5 + α), hence α^{2} + 4α − 4 = 0, and α = −2 + 2\sqrt{2}. Thus [3, \overline{1, 4}] = 3+(−2+2\sqrt{2}) = 1+2\sqrt{2}. As a check, type contfrac(1+2*sqrt(2)) into PARI.

(ii) Using PARI we quickly see that (1+\sqrt{23})/5 should equal [\overline{1, 6, 3, 1}]. To prove this, we have to do the algebra as in part (i). We have

α = [\overline{1, 6, 3, 1}] = 1 + \frac{1}{6 + _{\frac{1}{3+_{\frac{1}{1+ \frac{1}{α}}}}}} .

Using basic algebra, this simplifies to

α = \frac{22 + 29α}{19 + 25α}.

Thus

25α^{2} − 10α − 22 = 0,

so, since α > 0,

α = \frac{10 + \sqrt{100 + 4 · 22 · 25}}{50} = \frac{1}{5}(1 + \sqrt{23}),

as required.

6. If m were small, this problem would be completely trivial to solve using a simple PARI command like

  ss(n) = for(x=1,floor(sqrt(n)),if(issquare(n-x^2),print(x)))

However, ss(m) will take an extraordinarily long time to terminate, so instead we use the proof that integers of a certain form are a sum of two squares. First, factor m using, e.g., the PARI command factor:

m = 171255509 · 758572081 · 817611037.

Each of these three prime divisors is congruent to 1 modulo 4, so each is a sum of two squares. The following representations were found using the PARI command ss above:

171255509 = 4153^{2} + 12410^{2}
758572081 = 14460^{2} + 23441^{2}
817611037 = 17946^{2} + 22261^{2}

Now we use the formula (from Lecture 21) for expressing a product of two sums of two squares as a sum of two squares

(x_{1}^{2} + y_{1}^{2})(x_{2}^{2} + y_{2}^{2}) = (x_{1}x_{2} + y_{1}y_{2})^{2} + (x_{1}y_{2} − x_{2}y_{1})^{2},

which comes from multiplication in the Gaussian integers:

? (4153+12410*I)*(14460+23441*I)*(17946+22261*I)
%14 = -10304665980833 - 171525258172*I

Thus

106215561890727905176155473 = 10304665980833^{2} + 171525258172^{2}.

7. First, load the file forms.gp from Lecture 24. The command reducedforms computes a list of reduced forms of discriminant -888:

? r=reducedforms(-888)
%2 = [[1, 0, 222], [11, -6, 21], [11, 6, 21], [13, -10, 19],
      [13, 10, 19], [14, -8, 17], [14, 8, 17], [2, 0, 111],
      [3, 0, 74], [6, 0, 37], [7, -6, 33], [7, 6, 33]]

Thus the class group has order 12. Since composition(r[1],r[1]) is r[1], the form (1, 0, 222) is the identity of the group. There are exactly two isomorphism classes of abelian groups of order 12: one is represented by ℤ/3ℤ × ℤ/4ℤ and the other by ℤ/3ℤ × ℤ/2ℤ × ℤ/2ℤ. To decide which is our class group, we compute the order of each element.

? for(n=1,12,print1(orderform(r[n],r[1]),"   "))
1   6   6   6   6   6   6   2   2   2   3   3

Since no element has order 4, the class group must be

ℤ/3ℤ × ℤ/2ℤ × ℤ/2ℤ.

8. (i) One way to compute the values is to use that ellap is p + 1 − M_{p}:

? e = ellinit([0,-4,0,0,16])
? forprime(p=3,30,if(p!=11,print1(p+1-ellap(e,p),", ")))
   5, 5, 10, 10, 20, 20, 25, 30,
\\ 3  5   7  13  17  19  23  29

(ii) In PARI, one can compute the N_{n} as follows:

? q*prod(n=1,30,(1-q^n)^2)*prod(n=1,3,(1-q^(11*n))^2)  + O(q^30)
%22 = q - 2*q^2 - q^3 + 2*q^4 + q^5 + 2*q^6 - 2*q^7 - 2*q^9 - 2*q^10
        + q^11 - 2*q^12 + 4*q^13 + 4*q^14 - q^15 - 4*q^16 - 2*q^17
        + 4*q^18 + 2*q^20 + 2*q^21 - 2*q^22 - q^23 - 4*q^25 - 8*q^26
        + 5*q^27 - 4*q^28 + O(q^30)

(iii) The sums are

4, 6, 8, 14, 18, 24, 30,

so we conjecture that for p > 29, we have M_{p} + N_{p} = p + 1. (Note that we are not required to prove this!)

9. (i) Use the ellap function and that p + 1 − a_{p} = N_{p}:

? forprime(p=3,30,print1(p+1-ellap(e,p),"  "))
4  4  8  12  20  16  20  24  20

(ii) In the above examples, N_{p} = p + 1 for p ≡ 3 (mod 4), so we conjecture in general that this relation holds. We now prove this conjecture. Supposing p ≡ 3 (mod 4), we must count the number of points on y^{2} = x^{3} + x with coordinates in ℤ/pℤ. Since p ≡ 3 (mod 4), we have (\frac{−1}{p}) = −1, i.e., −1

is not a perfect square. Thus if x ∈ ℤ/pℤ and x^{3} + x is nonzero, then exactly one of x^{3} + x or −(x^{3} + x) = (−x)^{3} + (−x) is a perfect square. Since x^{3}+x = x(x^{2}+1) and, as just noted, x^{2}+1 has no root in ℤ/pℤ, the cubic is 0 only when x = 0. Thus the points on E are as follows: the point at infinity, the point (0, 0), and points (x, ±y) where x runs through exactly half of the nonzero elements of ℤ/pℤ. There are thus 1 + 1 + 2 · (p − 1)/2 = p + 1 points on E over ℤ/pℤ.

10. Your answer will depend on the random number seed in your version of PARI. We use the following functions from Lecture 31.

{ECM(N, m)= local(E);
E = ellinit([0,0,0,random(N),1]*Mod(1,N));
print("E: y^2 = x^3 + ",lift(E[4]),"x+1,  P=[0,1]");
ellpow(E,[0,1]*Mod(1,N),m);  \\ this fails if and only if we win!
}
{lcmfirst(B) =
local(L,i); L=1; for(i=2,B,L=lcm(L,i));
return(L);
}

I’m going to start with lcmfirst(10000), though you might have choosen something different for m.

? m = lcmfirst(10000);
? N = 124531325385603661726997;
? ECM(N,m)
E: y^2 = x^3 + 90450397866599611397131x+1,  P=[0,1]
***   impossible inverse modulo: Mod(495899, 124531325385603661726997).

We have thus split N:

N = 495899 · 251122356337890703.

Now apply ECM to the remaining factor:

? ECM(N/495899,m)
E: y^2 = x^3 + 35484437310832518x+1,  P=[0,1]
  ***   impossible inverse modulo: Mod(311221384171, 251122356337890703).

Thus

N = 495899 · 311221384171 · 806893.

The first and last factors are prime, but the middle one is composite:

? isprime(495899,1)
%5 = 1
? isprime(311221384171,1)
%6 = 0
? isprime(806893,1)
%7 = 1

When we try ECM on the second factor, it fails a few times, then succeeds:

? ECM(311221384171,m)
E: y^2 = x^3 + 246181556758x+1,  P=[0,1]
%8 = [0]
? ECM(311221384171,m)
E: y^2 = x^3 + 163571326944x+1,  P=[0,1]
%9 = [Mod(20641240315, 311221384171), Mod(200682828122, 311221384171)]
? ECM(311221384171,m)
E: y^2 = x^3 + 255080864418x+1,  P=[0,1]
  ***   impossible inverse modulo: Mod(888161, 311221384171).

Thus

N = 495899 · 888161 · 350411 · 806893,

and isprime reveals that these are all prime. As a lazy double check, we use the builtin factorization routine in PARI:

? factor(N)
%11 =
[350411 1]
[495899 1]
[806893 1]
[888161 1]

11. This is an extremely difficult open problem, and I have no idea how to solve it.