$n \in \mathbb{N}$ has at least 73 two-digit divisors. Prove that one of the divisors is 60.

Question

$n \in \mathbb{N}$ has at least 73 two-digit divisors.

I have these questions:

a) How can I prove that one of the two-digit divisors must be number 60?

b) How can I find a natural number that has $\mathbb{exactly}$ 73 two-digit divisors?

Answer 1

You're asking a wrong type of question in this kind of exercise. Use Dirichlet's principle instead:

1. Among those 73 divisors, there must be at least one that is divisible by 4.
2. Among 73 divisors at least one must be divisible by 3.
3. There are 18 two-digit numbers divisible by 5 ($10, 15, 20, 25, \dots, 90, 95$ and there are 90 two-digit numbers overall. If we remove those divisible by 5, there are 72 left, so among those 73, there must be the one divisible by 5.

Since the number is divisible by 3, 4 and 5, it's also divisible by $3*4*5=60$.

Answer 2

There are $90$ two digit numbers $45$ of then are odd. So at least $73 -45= 28$ of $73$ divisors are even. So $n$ has an even divisor and is even.

If the $45$ even two digit numbers $22$ of then them are divisible by $4$. So at least $28-22=6$ of these divisors are divisible by $4$ so $n$ is divisible by $4$.

Note: of the $22$ numbers divisible $4$, $11$ of them are divisible by $8$. But we only need $6$ divisible by $4$ and none of those need to be divisible by $8$ so we do not need any divisible by $8$.

Of the $90$ two digit numbers $30$ of the are divisible by $3$ and $60$ of them aren't. So there are of the $73$ divisors, at least, $73-60=13$ of them are divisible by $3$. So $n$ is divisible by $3$.

Of the $90$ two digit numbers $18$ of them are divisible by $5$ and $72$ of the aren't. So there are at least $73-72=1$ of the divisors divisible by $5$. So $n$ is divisible by $5$.

So $n$ is divisible by $4$ and $3$ and $5$ so $n$ is divisible by $\operatorname{lcm}{4,3,5) = 60$.

......

Give me a moment to think about b).

Answer 3

For (b), you need to remove 17 two-digit numbers from the 90 available. Remove 9 of the 10 primes between 50 and 100, and then remove the four primes between 34 and 50 together with their doubles. For example, remove $$37, 74, 41, 82, 43, 86, 47, 94, 53, 59, 61, 67, 71, 73, 79, 83, 89.$$ Clearly the product of the remaining two-digit numbers is not divisible by any of these, so it has exactly 73 two-digit divisors.

Edit: changed after reading @WillJagy's comment. I miscounted the number of possible two-digit divisors.

Answer 4

I tried the answer by roger1, this slight change makes it work: $$ 588300074488526400 \; = \; 2^6 \cdot 3^4 \cdot 5^2 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 97 $$

---

588300074488526400 =  2^6 3^4 5^2 7^2 11 13 17 19 23 29 31 97


10    count 1
11    count 2
12    count 3
13    count 4
14    count 5
15    count 6
16    count 7
17    count 8
18    count 9
19    count 10
20    count 11
21    count 12
22    count 13
23    count 14
24    count 15
25    count 16
26    count 17
27    count 18
28    count 19
29    count 20
30    count 21
31    count 22
32    count 23
33    count 24
34    count 25
35    count 26
36    count 27
38    count 28
39    count 29
40    count 30
42    count 31
44    count 32
45    count 33
46    count 34
48    count 35
49    count 36
50    count 37
51    count 38
52    count 39
54    count 40
55    count 41
56    count 42
57    count 43
58    count 44
60    count 45
62    count 46
63    count 47
64    count 48
65    count 49
66    count 50
68    count 51
69    count 52
70    count 53
72    count 54
75    count 55
76    count 56
77    count 57
78    count 58
80    count 59
81    count 60
84    count 61
85    count 62
87    count 63
88    count 64
90    count 65
91    count 66
92    count 67
93    count 68
95    count 69
96    count 70
97    count 71
98    count 72
99    count 73
Sat Jan 11 15:07:58 PST 2020

---