practice problems pending

 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 + p3 = 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. 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




Comments

Post a Comment

Popular posts from this blog

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more

IOQM 2023 solutions

Image
Q1. Let n be a positive integer such that 1 ≤ n ≤ 1000 . Let M n be the number of integers in the set X n = { 4 n + 1 , 4 n + 2 , … , 4 n + 1000 } . Let a = max ⁡ { M n : 1 ≤ n ≤ 1000 } , and b = min ⁡ { M n : 1 ≤ n ≤ 1000 } . a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}. Find a − b a - b . Solution: Quick tip: If n^2 = k then (n+1)^2 = k + (2n + 1) We will use this here. Also as the numbers grow larger the gap between 2 perfect squares becomes less and less. For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200. So X1 = {sqrt(5) ... sqrt(1004)} will have the most number of perfect squares. While X1000 = {sqrt(4001)...sqrt(5000)} will have the least. In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31. Total: 31 - 3 + 1 = 29 integers in X1. In X1000, We know that 64^2 = 4096 so 64 is the first integer. 70^2 = 4900 and ...
Read more

Simon's factoring trick(complete the rectangle)

  "Complete the Rectangle" , also called Simon’s Favorite Factoring Trick , is a clever algebraic method for factoring expressions of the form: x y + a x + b y + c xy + ax + by + c Or more commonly, you'll see it used in a simpler form: x y + a x + b y + d xy + ax + by + d But especially when we’re given something like: x y + a x + b y + a b xy + ax + by + ab It becomes very easy to factor. Let me walk you through it step-by-step. 💡 The Key Idea We add and subtract a constant to turn the expression into a perfect rectangle (a.k.a. a factorable quadratic or product of binomials). The “complete the rectangle” version of this trick usually works best on expressions like: x y + a x + b y + a b xy + ax + by + ab We treat it like this: x y + a x + b y + a b = ( x + b ) ( y + a ) xy + ax + by + ab = (x + b)(y + a) ✅ Step-by-Step Example Factor: x y + 3 x + 2 y + 6 xy + 3x + 2y + 6 Step 1: Rearrange the terms: Group like this: x y + 3 x + 2 y + 6 xy + 3x + ...
Read more