How many divisors of $30^{2003}$ are there which do not divide $20^{2000}$?
Problem
Source:
Tags: number theory, combinatorics
tenebrine
10.04.2021 02:07
If the divisor is a multiple of $3$ then it works.
This happens in $2003 \times 2004 \times 2004$ ways.
Otherwise, it must have the power of $5$ be higher than $2000$.
The power of $5$ may be $2001$, $2002$, or $2003$, so for this case there are $3 \times 2004$ divisors.
The sum is $8044086060$.
Leo2020
10.04.2021 02:12
are you kidding me this isn't really 1st grade right??
judgefan99
10.04.2021 02:12
no way this is 1st grade. Maybe 11th grade.
natmath
10.04.2021 02:35
tenebrine wrote:
If the divisor is a multiple of $3$ then it works.
This happens in $2003 \times 2004 \times 2004$ ways.
Otherwise, it must have the power of $5$ be higher than $2000$.
The power of $5$ may be $2001$, $2002$, or $2003$, so for this case there are $3 \times 2004$ divisors.
The sum is $8044086060$.
Are you sure you didn't double count where the powers of 5 are higher and its a multiple of $3$? Also @2above, I think someone mentioned this in a different post, but the grades in this context don't mean school grades but are rather a level of difficulty. I think these olympiads range from grade 1 to grade 4 maybe where the higher grade corresponds to a higher difficulty. However, these are not school grades but just "grades of difficulty." @below nevermind I misread part of your solution
tenebrine
10.04.2021 02:38
I don't think it overcounts, I considered where the power of 5 was higher already assuming it was not a multiple of 3
natmath
10.04.2021 02:49
There are $2^{2003}\cdot 3^{2003}\cdot 5^{2003}\implies 2004^3$ divisors in $30^{2003}$
These divisors can be represented as $2^{a_1}3^{a_2}5^{a_3}$, where $a_i\in [0,2003]$
Since $20^{2000}=2^{4000}\cdot 5^{2000}$, a divisor of $30^{2003}$ is only a divisor of $20^{2000}$ is $a_1\leq 4000$, $a_2\leq 0$, and $a_3\leq 2000$. There are $2004\cdot 1\cdot 2001$ ways to do this.
Hence our answer is
$$2004^3-2004\cdot 2001=8044086060$$