practice problems

Q. Let S be the sum of the base 10 logarithms of all the proper divisors of 1000000. What is the integer nearest to S?

Solution:
Before that prove that product of divisors of an integer N is P = N^(d(N)/2) where d(N) = number of divisors of N.
Let there be k divisors of N which are 1 = d1, d2, ... dk = N. So k = d(N).
If we multiply them pairwise d1.dk = N = d2.d(k-1) = dk.d1
Multiply all together.
(d1.d2..dk)^2 = N^k = P^2 => P = N^(k/2) H.P.

Now:
S = log(d1) + log(d2)... log(dk) = log(d1.d2...dk) = log(N^(k/2)) = (k/2).log(N) = (1/2).k.6 = 3.k
k = number of divisors = 7*7
So S = 49*3 = 147
But from this we need to subtract log of improper divisor(number itself).
Answer = 147 - 6 = 141

Q. For k≥2, show each of the following:

(a) 

n=2^(k−1) satisfies the equation σ(n)=2n−1.

(b) If 2^k −1 is prime, then 

n=2^(k−1)(2^k−1) satisfies the equation σ(n)=2n.

(c) If 2^k −3 is prime, then 

n=2^(k−1)(2^k −3) satisfies σ(n)=2n+2.

Solution:
(a) Do the sum of the GP 1 + 2 + ... 2^(k-1)
(b) Use the fact that for co prime a,b, sigma(a.b) = sigma(a).sigma(b)
(c) Again use the same property as in (b)

Q. 

Solution:
First hand solve it for n = 3.
Both sides should equal 8.

Q.

Solution:
768 = 3.2^8 sigma(768) = 4.(2^9 - 1) f(768) = 4.(2^9 - 1)/3.2^8
384 = 3.2^7 sigma(384) = 4.(2^8 - 1) f(384) = 4.(2^8 - 1)/3.2^7
f(768) - f(384) = 1/192

Q.

Solution:

Q.

Solution:
If n divides 3^12 - 1 and 3^k - 1 both where 1<=k<=11
then it will also divide their gcd. Proof here.

gcd(3^12 - 1, 3^k - 1) = 3^gcd(12,k) - 1 Proof here.
So
'n' will divide 3^gcd(12,k) - 1.

Possible gcds of (12,k) = 1,2,3,4,6 for 1 <= k <= 11

Using difference of powers theorem we can say that,

if 'n' divides 3^p - 1, it will also divide 3^q - 1 where q is a multiple of p.
So
if we find all the divisors of 3^4 - 1 and 3^6 - 1, that list will also include all the divisors of 3^1 - 1, 3^2 - 1, 3^3 - 1.

So now our task is to find all the divisors of 3^4 - 1 and 3^6 - 1 and remove them from the divisors of 3^12 - 1.

3^12 - 1 = (3^6 - 1)(3^6 + 1) = 26.28.730 = 2.13.2^2.7.73.5.2 = 2^4.5.7.13.73
3^4 - 1 = 80 = 2^4.5
3^6 - 1 = 728 =  2^3.7.13


Total divisors of 3^12 - 1 = 5.16 = 80
Total odd divisors = 16
Total even divisors = 64


Odd divisors of 80 = 1,5
Even divisors of 80 = 2,4,8,16,10,20,40,80 => total 8

Odd divisors of 728 = 1,7,13,91
Even divisors of 728 = 2,4,8 and others which are multiples of 7 and/or 13 => total 12

Total unique odd divisors to be removed = 5 which are 1,5,7,13,91
Total unique even divisors to be removed = 8 + 12 - 3 = 17

So finally valid odd divisors = 16 - 5 = 11
valid even divisors = 64 - 17 = 47
Answer.

In the solution above, we didn't consider common divisors of 3^5-1,3^7-1,3^8-1,3^9-1,3^10-1,3^11-1. Why?
Because as we mentioned earlier:
gcd(3^12 - 1, 3^k - 1) = 3^gcd(12,k) - 1
=>
gcd(3^12 - 1, 3^5 - 1) = 3^gcd(12,5) - 1 = 3^1 - 1
gcd(3^12 - 1, 3^7 - 1) = 3^gcd(12,7) - 1 = 3^1 - 1
gcd(3^12 - 1, 3^8 - 1) = 3^gcd(12,8) - 1 = 3^4 - 1
gcd(3^12 - 1, 3^9 - 1) = 3^gcd(12,9) - 1 = 3^3 - 1
gcd(3^12 - 1, 3^10 - 1) = 3^gcd(12,10) - 1 = 3^2 - 1
gcd(3^12 - 1, 3^11 - 1) = 3^gcd(12,11) - 1 = 3^1 - 1

So all these numbers have been already considered by us.

Q. Find the form of all positive integers n satisfying τ(n)=10. What is the smallest positive integer for which this is true? τ(n) is totient function.
Solution:
Let's call it phi(n).
10 = phi(n)
= p1^k1.p2^k2.p3^k3.(1- 1/p1)(1-1/p2)(1-1/p3)...
= p1^(k1-1).p2^(k2-1).(p1-1).(p2-1)...

=> each of (p1-1),(p2-1),... will divide 10.
So possible prime factors are p-1 = 1,2,5,10 => p = 2,3,6,11
Since 6 is not a prime, p = 2,3,11
And
n is of the form: 2^a.3^b.11^c
Since  2^a,3^b,11^c are pairwise co-primes
=> phi(n) = phi(2^a).phi(3^b).phi(11^c)

1. Consider 3^b
phi(3^b) = (3-1).3^(b-1) = 2.3^(b-1)
b has to be 1 since 10 is not divisible by 3.
So phi(3^b) = 2
=> phi(2^a).phi(11^c) = 5
But phi(n) is always even except for phi(1) and phi(2). Why? Because (p-1) is a factor and each prime except 2 is odd hence phi(n) is even.
So b = 0
=> phi(n) = phi(2^a).phi(11^c) and n = 2^a.11^c
if c = 0 then n = 2^a and phi(n) = (2-1).2^(a-1) which can never be 10.
If c >= 2 then phi(11^c) = 10.11^(c-1) > 10
So c = 1
phi(11^c) = 10 and phi(2^a) = 1
n = 2^a.11
phi(2^a) = 1 => a = 0,1 => phi(1) = 1 = phi(2)
=> n = 1.11, 2.11 = 11,22 Answer.

Q. Show that there are no positive integers n satisfying σ(n)=10.
Hint: Note that for n>1 σ(n)>n.
Solution:
Extending the hint, sigma(n) >= n + 1 (since 1,n are divisors of n).
Now we can check for n = 1 to 9 and show that none of them equals 10.

Another algebraic way is this:

sigma(n) = (1+p+p^2...p^a)(1+q+q^2..q^b)...
If n = p^a.q^b... where p,q... are prime.

For it to be 10 each of the polynomials should divide 10 which has 1,2,5,10 as divisors.
Since each of them is more than 1 and smallest prime is 2 => each factor is >= 3
So we can't build 10 with 2 as one factor and 5 as another.
There will have to be a single polynomial adding upto 10.
And n = p^a, i.e. only one prime factor.
Let's try with a = 1
n = 1 + p = 10 => p = 9.No.
a = 2
1 + p + p^2 = 10 => p(p+1) = 9. No. should be even.
a = 3
1 + p + p^2 + p^3 = 10 not possible since even with smallest prime 2, it exceeds 10.

Q. Show that sigma(a.b) = sigma(a).sigma(b) where sigma is sum of divisors and a,b are coprime.

Q. If n and (n+2) are twin primes, establish that sigma(n+2) = sigma(n) + 2.

Solution:
simple enough.