Maths Olympiad Prep

Library / /183 of 520

Number theory Difficulty 6.7 National olympiad Find the answer

For all positive integers nn, denote by σ(n)\sigma(n) the sum of the positive divisors of nn and νp(n)\nu_p(n) the largest power of pp which divides nn. Compute the largest positive integer kk such that 5k5^k divides dNν3(d!)(1)σ(d),\sum_{d|N}\nu_3(d!)(-1)^{\sigma(d)}, where N=61999N=6^{1999}.

Proposed by David Altizio

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. Understanding the Problem:
We need to compute the largest positive integer k k such that 5k 5^k divides the sum
dNν3(d!)(1)σ(d), \sum_{d|N} \nu_3(d!)(-1)^{\sigma(d)},
where N=61999 N = 6^{1999} .

2. **Analyzing σ(d) \sigma(d) :**
Note that σ(d) \sigma(d) is odd precisely when d d is a power of 2 times an odd square. Since d d divides 61999 6^{1999} , this is equivalent to saying ν3(d) \nu_3(d) is even. Therefore, we have (1)σ(d)=(1)ν3(d)+1 (-1)^{\sigma(d)} = (-1)^{\nu_3(d) + 1} .

3. **Rewriting the Sum S S :**
Let S S be the sum in question. We can write:
S=k=01999n=01999(1)n+1ν3((2k3n)!). S = \sum_{k=0}^{1999} \sum_{n=0}^{1999} (-1)^{n+1} \nu_3((2^k \cdot 3^n)!).

4. Using Legendre's Formula:
Legendre's formula gives:
ν3((2k3n)!)=2k3n3+2k3n32+2k3n33+. \nu_3((2^k \cdot 3^n)!) = \left\lfloor \frac{2^k \cdot 3^n}{3} \right\rfloor + \left\lfloor \frac{2^k \cdot 3^n}{3^2} \right\rfloor + \left\lfloor \frac{2^k \cdot 3^n}{3^3} \right\rfloor + \cdots.
Simplifying, we get:
ν3((2k3n)!)=2k(3n1+3n2++1)+ν3((2k)!). \nu_3((2^k \cdot 3^n)!) = 2^k \left(3^{n-1} + 3^{n-2} + \cdots + 1\right) + \nu_3((2^k)!).
This can be further simplified to:
ν3((2k3n)!)=2k1(3n1)+ν3((2k)!). \nu_3((2^k \cdot 3^n)!) = 2^{k-1}(3^n - 1) + \nu_3((2^k)!).

5. **Summing Over n n :**
We now sum over n n :
n=01999(1)n+1(2k1(3n1)+ν3((2k)!)). \sum_{n=0}^{1999} (-1)^{n+1} \left(2^{k-1}(3^n - 1) + \nu_3((2^k)!)\right).
This simplifies to:
2k1n=01999(1)n+1(3n1). 2^{k-1} \sum_{n=0}^{1999} (-1)^{n+1} (3^n - 1).

6. Using the Geometric Series Formula:
The sum of the geometric series is:
n=01999(1)n+13n=3(1(3)2000)1(3)=3200014. \sum_{n=0}^{1999} (-1)^{n+1} 3^n = \frac{3(1 - (-3)^{2000})}{1 - (-3)} = \frac{3^{2000} - 1}{4}.
Therefore, the sum becomes:
2k13200014=2k3200018. 2^{k-1} \cdot \frac{3^{2000} - 1}{4} = 2^k \cdot \frac{3^{2000} - 1}{8}.

7. **Summing Over k k :**
We now sum over k k :
S=3200018k=019992k=3200018(220001). S = \frac{3^{2000} - 1}{8} \sum_{k=0}^{1999} 2^k = \frac{3^{2000} - 1}{8} \cdot (2^{2000} - 1).

8. Using the Lifting The Exponent (LTE) Lemma:
Applying the LTE lemma, we get:
ν5(S)=ν5(320001)+ν5(220001). \nu_5(S) = \nu_5(3^{2000} - 1) + \nu_5(2^{2000} - 1).
Using the properties of the LTE lemma:
ν5(320001)=ν5(815001)=ν5(811)+ν5(500)=1+3=4, \nu_5(3^{2000} - 1) = \nu_5(81^{500} - 1) = \nu_5(81 - 1) + \nu_5(500) = 1 + 3 = 4,
and
ν5(220001)=ν5(165001)=ν5(161)+ν5(500)=1+3=4. \nu_5(2^{2000} - 1) = \nu_5(16^{500} - 1) = \nu_5(16 - 1) + \nu_5(500) = 1 + 3 = 4.
Therefore,
ν5(S)=4+4=8. \nu_5(S) = 4 + 4 = 8.

The final answer is 8 \boxed{8} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.