MA357, Spring 2008
Comments on Problem Set 5

Now notice that if x² ≡ 1 (mod m), then also (–x)² ≡ 1 (mod m). So we can pair each solution with its negative. We don't need to worry about the possibility that x ≡ –x (mod m), because that amounts to 2x ≡ 0 (mod m) which forces gcd(x,m)>1 unless m = 2, which is a prime and so falls under the case we've already handled. But if b² ≡ 1 (mod m), then b*(–b)≡–b² ≡ –1 (mod m), so each pair contributes a –1. So we're left with a product of –1s, which has to be congruent to either 1 or –1.

With a little bit of group theory and a little more information about the structure of the integers (mod m), one can show that the product will be –1 when m is 4, a prime power, or twice a prime power, and it will be 1 otherwise.

2. For part (a), notice that F(x) is equal to x/5 whenever x is a multiple of 5, and in fact is always within 1 of x/5. Hence the limit of F(x)/x as x goes to infinity is 1/5, justifying the statement.

For (b), pretty much the same thing happens: S(x) = x^1/2 – E, where E is between 0 and 1. Hence the limit of S(x)/x as x goes to infinity is zero, which says that most numbers are not squares.

3. In each case, it makes sense to do two things: first, consider whether the expression factors; if it does, then it's unlikely to be equal to a prime. Second, run some tests on the computer.

Neither N² + 2 nor N² – 2 factors. On the other hand N² + 3N + 2 = (N+1)(N+2), so this expression is certain not to be a prime unless N = 0. For the last one, N² + 2N + 2 = (N+1)² + 1, which means this is just the N² + 1 case in disguise. So from this we would guess that the answer is "yes" for a, b, and d, and no for c.

Of course, a GP check is easy to do:

? for(n=1,1000,if(isprime(n^2–2),print(n)))

? for(n=1,1000,if(isprime(n^2+2),print(n)))

4. The easiest way to do this is by the magic of convolutions, using part (b) of problem 11 in the midterm: σ = i*u and both i and u are multiplicative, so there!

Otherwise, we do it by hand. The point is to note that when gcd(m,n)=1 there is a bijection between two sets:

{divisors d of mn}

and

{pairs (u,v) where u divides m and v divides n}

The correspondence is just (u,v) → uv. It's clear that uv is a divisor of mn; what we need to check is that every divisor can be written this way and that this correspondence is one-to-one. Both things are easily checked using the prime factorization of mn. (Alternatively, one could define, for a divisor d of mn, u=gcd(d,m) and v=gcd(d,n) and prove that d → (u,v) is then the inverse function. It's a nice challenge to do this. Notice that the hypothesis that gcd(m,n)=1 is essential!)

Once we have that, it's easy: σ(n) is the sum of all possible choices for u, σ(n) is the sum of all possible choices for v. So their product is the sum of all possible products uv. By the correspondence above, that's the sum of all possible divisors of mn, and so is σ(mn).

5. Here's the script of the GP session:

? isprime(463)            // is it prime?
%1 = 1                    // yes, so the phi is 462
? bezout(113,462)         // find the r and s
%2 = [-139, 34, 1]
? -139+462                // it's negative, so add 462 to it
%3 = 323
? Mod(347,463)^323        // take that power
%4 = Mod(37, 463)         // that's the answer

? Mod(37,463)^113         // let's check to make sure it works
%5 = Mod(347, 463)        // yes!

? eulerphi(588)
%6 = 168
? bezout(275,%)
%7 = [11, -18, 1]
? Mod(139,588)^11
%8 = Mod(559, 588)
? Mod(559,588)^275
%9 = Mod(139, 588)

6. This is my favorite problem in this set, because it involves such slippery logic. We'll prove that there is no such m. First of all, m must be a divisor of 2^m – 1, hence it must be odd. Let p be any prime divisor of m. Then 2^m = 1 (mod p), so that the order of 2 (mod p) must be a divisor of m. On the other hand, this order must, as we know, be a divisor of p – 1. Since the order is not 1, we see that m and p – 1 must have a common divisor, that is, gcd(m,p–1) > 1.

So we've proved that m is odd and that for any prime divisor p of m we must have gcd(m,p–1) > 1. We claim this is a contradiction. To see this, let q be the smallest prime divisor of m. Then q > 2, so q – 1 > 1. The prime factorization of q – 1 must involve only primes smaller than q, which, since q is the smallest divisor of m, cannot divide m. Hence we have gcd(m,q–1) = 1, which contradicts our result above.

The conclusion, then is that no such m exists. (Notice that knowing that m is odd is crucial for this argument to work; do you see why?)

7. Notice that 2ⁿ = 1 (mod 2ⁿ – 1), and that any smaller power of 2 is smaller than 2ⁿ – 1, hence can't be congruent to 1. Hence, the order of 2 (mod 2ⁿ – 1) is n. Since the order of 2 is a divisor of φ(n), the conclusion follows. 8. Problem 18.1 is lots of work if done by hand, but not difficult. The message is "FERMAT".

For Problem 18.2, let's do parts (a) and (b) together. So let m be a product of distinct primes p, q, r, s,... Let a be any number less that m. We have encryption and decription exponents e and d, and we know that e is any number relatively prime to φ(m) and that d is a positive number such that ed = 1 + vφ(m) for some integer v. Notice that

What we need to show is that a^ed = a (mod m) even if a and m have a common factor.

Since m = pqrs... and the primes are distinct, it's enough to prove the congruence we want for each prime divisor of m. So what is a^ed equal to (mod p)?

There are two possibilities: either a is divisible by p, or it is not. If it isn't, then by Little Fermat we have a^p–1 = 1 (mod p). Since p–1 is a divisor of φ(m), that implies that a^φ(m) = 1 (mod p), and therefore, using the fact that ed = 1 + vφ(m), we see that a^ed = a (mod p).

The other possibility is that p does divide a. But then a^ed = a (mod p) is still true because both sides are just 0 (mod p).

So in any case we have a^ed = a (mod p) for every prime divisor p of m, hence a^ed = a (mod m), which is what we wanted to prove.

Part (c) is easy.

9.The first message is a quote from Gauss:

Mathematics is the queen of science, and number theory is the queen of mathematics. K. F. Gauss.

gp -p 20000000

This starts GP with a list of precomputed primes up to about 20 million. The idea is that having lots of precomputed primes makes it easier to factor.

? factor(956331992007843552652604425031376690367)
%1 =
[7746289204980135457 1]

[123456789012345681631 1]

? %[1,1]
%2 = 7746289204980135457

? %1[2,1]
%3 = 123456789012345681631

? p=%2
%4 = 7746289204980135457

? q=%3
%5 = 123456789012345681631

Ok, I've got the factorization, now I'll enter the exponent and find its inverse modulo phi(pq) = (p – 1)(q – 1). I could use the GP function eulerphi, but it's easy enough to do it by hand.

? k=12398737
%6 = 12398737

? Mod(k,(p-1)*(q-1))
%7 = Mod(12398737, 956331992007843552521401346814050873280)

? %^(-1)
%8 = Mod(801756262003467870842260800571951669873,
         956331992007843552521401346814050873280)

? d=lift(%)
%9 = 801756262003467870842260800571951669873

"Lift" just means to make an integer out of an "integermod". Now let's enter the five numbers in our message, then raise each to the d-th power (mod pq). Notice that we type Mod(m1,p*q)^d and not Mod(m1^d,p*q), because we want GP to know that it's working in the mod pq world, and not to try to compute the integer m1^d.

? m1=821566670681253393182493050080875560504
%10 = 821566670681253393182493050080875560504

? m2=87074173129046399720949786958511391052
%11 = 87074173129046399720949786958511391052

? m3=552100909946781566365272088688468880029
%12 = 552100909946781566365272088688468880029

? m4=491078995197839451033115784866534122828
%13 = 491078995197839451033115784866534122828

? m5=172219665767314444215921020847762293421
%14 = 172219665767314444215921020847762293421

? Mod(m1,p*q)^d
%15 = Mod(30181514191616152815243012281124131815,
          956331992007843552652604425031376690367)

? c1=lift(%)
%16 = 30181514191616152815243012281124131815

? Mod(m2,p*q)^d
%17 = Mod(29251611281930182315301913281526221915,
          956331992007843552652604425031376690367)

? c2=lift(%)
%18 = 29251611281930182315301913281526221915

? Mod(m3,p*q)^d
%19 = Mod(14301815232513213031283022151123121930,
          956331992007843552652604425031376690367)

? c3=lift(%19)
%21 = 14301815232513213031283022151123121930

? Mod(m4,p*q)^d
%22 = Mod(19252414192930281113301925243117221916,
          956331992007843552652604425031376690367)

? c4=lift(%)
%23 = 19252414192930281113301925243117221916

? Mod(m5,p*q)^d
%24 = Mod(19131130192524112414141528192919252434,
          956331992007843552652604425031376690367)

? c5=lift(%)
%25 = 19131130192524112414141528192919252434

OK, that was it with GP. I then cut-and-pasted the numbers into a text editor to decode the message. Inserting spaces, we get:

30 18 15 14 19 16 16 15 28 15 24 30 12 28 11 24 13 18 15 
29 25 16 11 28 19 30 18 23 15 30 19 13 28 15 26 22 19 15
14 30 18 15 23 25 13 21 30 31 28 30 22 15 11 23 12 19 30
19 25 24 14 19 29 30 28 11 13 30 19 25 24 31 17 22 19 16
19 13 11 30 19 25 24 11 24 14 14 15 28 19 29 19 25 24 34

Using search-and-replace 26 times, this translates to:

T H E D I F F E R E N T B R A N C H E 
S O F A R I T H M E T I C R E P L I E
D T H E M O C K T U R T L E A M B I T
I O N D I S T R A C T I O N U G L I F
I C A T I O N A N D D E R I S I O N X

Or (deleting the final X which is just a place holder, and putting spaces and punctuation back in):

"The different branches of arithmetic," replied the mock turtle, "ambition, distraction, uglification, and derision."

This, of course, is a famous passage from Alice in Wonderland.

10. As the assignment indicates, I think it's easier to use the results in the test about the * operation, and to note that G = λ * u, where u, as in the test is the function such that u(n) = 1 for all n. Then, from the test, we know that if λ is multiplicative then so is G.

It's easy to see that the λ function is multiplicative, so we can conclude that so is G, and this makes it fairly easy to understand the G function.

If you'd like to check it specifically in this case, here it is. The crucial point is to note that if n and m are relatively prime then any divisor of nm can be expressed uniquely as rs, where r|m and s|n. This is pretty clear from prime factorizations, and we used it in our solution for 15.1. Then it's just a matter of multiplying together the formulas

So now we know that G(n) is multiplicative. But on a prime power p^k we have:

11. Part (a) is pretty easy: just take powers of 2 or 3 modulo the indicated m until we get 1. The answers, in order, are 6, 4, 4, 4. Part (b) is something we had done in class, but I want you to really know this: the least exponent e_m(a) divides any exponent d such that 2^d = 1 (mod m). Since d=phi(m) works, it is divisible by e_m(a).

12. Most of you found the formula for e_mn: if gcd(m, n) = 1, then

Conversely, if t is a multiple of e_m, we have

For part (e), the natural conjecture is

So we know that e_p^k is divivible by e_p and a divisor of p^k–1e_p. So it must be equal to pⁱe_p for some i. But to prove the full conjecture we would need to prove that no value of i smaller than k – 1 works. But is that true?

Consider the following GP computation, which uses the function "znorder", which gives the least exponent for an "integermod".

? a=Mod(2,1093)
%1 = Mod(2, 1093)

? b=Mod(2,1093^2)
%2 = Mod(2, 1194649)

? znorder(a)
%3 = 364

? znorder(b)
%4 = 364

So it turns out that e_1093² = e₁₀₉₃ instead of being equal to 1093e₁₀₉₃. Sometimes small numbers are misleading!

(I have no idea, by the way, whether this is the smallest example, but I suspect it is.)

13. Start by noticing that for any number a not divisible by p or q, we will have a^k = 1 (mod pq) if and only if we have both a^k = 1 (mod p) and a^k = 1 (mod q). If k is any multiple of p – 1, the first congruence holds, and if k is any multiple of q – 1, the second congruence holds. So if k is any common multiple of (p – 1) and (q – 1) we will have a^k = 1 (mod pq). Now note that both (p – 1) and (q – 1) are even, so that e = (p – 1)(q – 1)/2 is a common multiple, and so, for any a, we have a^e = 1 (mod pq). But phi(pq) = (p – 1)(q – 1) > e, and so there is no primitive root (mod pq).

You could also use your result from problem 21.3, part d.