Problems for Number Theory September 16, 1998

62. Notice that while 2 | 2^{2} − 2, 3 | 2^{3} − 2, 5 | 2^{2} − 2, and 7 | 2^{7} − 2, it is not true that 4 | 2^{4} − 2 or that 6 | 2^{6} − 2. What’s going on here? When does n | 2^{n} − 2?

63. What if you try n | 3^{n} − 3? And 4? And arbitrary base a?

64. What is the greatest common divisor of 2^{n} − 1 and 2^{m} − 1?

65. What is the greatest common divisor of 3^{n} − 1 and 3^{m} − 1? Prove the obvious generalization.

66. (Hill’s Conjecture) If p is an odd prime, any prime which divides 2^{p} − 1 must be of the form 2kp + 1 for some number k.

67. If q = 2m + 1 is prime (m is not necessarily prime), then q divides either 2^{m} − 1 or 2^{m} + 1.

68. Gather data and formulate a conjecture which explains under what conditions q|2^{m} − 1 in the above. Prove it.

69. Formulate Hill’s other conjecture about composite Mersenne primes. (Hint: It is a trivial corollary of the previous conjecture when that is formulated correctly.) Prove it. Let’s change the subject. (We’ll come back with some tools, later.)

70. Solve the 12 linear congruences ax ≡ 1 (mod 13) for 1 ≤ a ≤ 12. Note how the solutions are paired. Does the same thing happen for 14? When is it guaranteed to happen? State and prove the appropriate theorem.

71. If p is prime, then (p − 1)! + 1 ≡ 0 (mod p).

72. If (n − 1)! + 1 ≡ 0 (mod n), then n is prime. Why is this not a practical primality test?

73. Solve the quadratic congruences x^{2}+1 ≡ 0 (mod 29), x^{2}+1 ≡ 0 (mod 41), and x^{2}+1 ≡ 0 (mod 43).

74. The quadratic congruence x^{2} + 1 ≡ 0 (mod p), p an odd prime, has a solution if and only if, p ≡ 1 (mod 4).

75. Let τ(n), denote the function whose value at n is the number of positive divisors of n (including 1 and n). Prove that τ(n) is odd if and only if n is a perfect square.

76. Prove that the product of all the positive divisors of n is n^{τ(n)/2}.

77. Prove that if gcd(m, n) = 1, then τ(mn) = τ(n)τ(m). A number-theoretic function with this property is said to be multiplicative.

78. Given a number k > 1, show that there exist infinitely many numbers n such that τ(n) = k. Find all numbers which satisfy τ(n) = 10.

79. Let σ(n) denote the function whose value at n is the sum of the divisors of n (including 1 and n). Prove that σ(n) is multiplicative.

80. Characterize those numbers for which σ(n) is odd.

81. Prove that if f(n) denotes the number of divisors function, then f(n) is multiplicative.

82. Euler’s phi function, ϕ(n), enumerates the number of integers less than n and relatively prime to it. For example, ϕ(2) = 1, ϕ(6) = 2, ϕ(15) = 8. Note that, by convention, ϕ(1) = 1. Prove that ϕ(n) is multiplicative.

83. Find all n such that ϕ(n) is odd.

84. Find a formula for ϕ(p^{n}) for prime p.

85. Find a quick way to evaluate ϕ(n) given that the prime factorization of n.

86. When is it true that ϕ(3n) = 3ϕ(n)? How about ϕ(2n) = n?

87. Given a number k show that there are only a finite number of solutions to ϕ(n) = k.

88. Prove that this finite number is zero, if k = 14. Even better, prove that this finite number is zero, if k is twice a prime and k+1 is composite.

89. For each number n > 1,

n = ∑_{d|n} ϕ(d),

where the sum is taken over the divisors of n.

90. If gcd(a, n)=1, then a^{ϕ(n)} ≡ 1 (mod n).