A positive integer $N$ is called northern if for each digit $d > 0$, there exists a divisor of $N$ whose last digit is $d$. How many northern numbers less than $2016$ are there with the fewest number of divisors as possible?
Problem
Source: Mathematics Regional Olympiad of Mexico Northeast 2016 P6
Tags: number theory, Digits
13.09.2022 00:54
parmenides51 wrote: A positive integer $N$ is called northern if for each digit $d > 0$, there exists a divisor of $N$ whose last digit is $d$. How many northern numbers less than $2016$ can they have as few divisors as possible? What's the question asking for? Was there a mistake in translation?
13.09.2022 01:40
, I used Google Translate as I do not speak Spanish
Attachments:

13.09.2022 04:51
I'm not fluent in Spanish, but I think the question is asking: "How many northern numbers less than $2016$ are there with the fewest number of divisors as possible?" So this is basically a two-part question: identifying the fewest possible number of divisors a number can have if it is northern, and then finding how many northern numbers there are less than $2016$ with that amount of divisors. ¡Vámonos! We claim that a northern number has at least $16$ divisors. A construction would be $270$ (divisors ending in each digit are $1, 2, 3, 54, 5, 6, 27, 18, 9$). Suppose FTSoC there is a northern number with fewer than $16$ divisors. Note that because it has a divisor ending in $2$ and $5$, clearly it must be divisible by $2$ and $5$. Now if it had at least four distinct prime divisors, then it would have at least $2^4 = 16$ divisors, contradiction. Therefore, it has at most one other prime divisor, call it $p$. If it was divisible by $p^3$, then it would have at least $2 \cdot 2 \cdot 4 = 16$ divisors, contradiction. Therefore, it must be divisible by at most $p^2$. Note that we still need it to be divisible by a number ending in $3$, $7$, and $9$. Any number divisible by $2$ or $5$ clearly cannot satisfy this, but the only divisors not of this form (besides $1$ of course) are $p$ and $p^2$. That's only two numbers and we still have three ending digits we haven't fulfilled yet, so this is impossible. Therefore, a northern number must have at least $16$ divisors. Now it's time to find how many northern numbers less than $2016$ there are with $16$ divisors. Note that we already know that a northern number is divisible by $2$ and $5$. Clearly it must have at least one other prime divisor. But if it only has one, say $p$, then it has to be in the form $2 \cdot 5 \cdot p^3$ (the other forms would fail for reasons explained before). We see that $p = 3$ works perfectly as shown before, and the next contender would be $p = 7$, but $2 \cdot 5 \cdot 7^3 > 2016$, so there's only one desired northern number in this case. If it has two other prime divisors, then it would have to be in the form $2 \cdot 5 \cdot p \cdot q$, where $p$ and $q$ are primes. Note that because the $2$ and the $5$ have to be excluded here, then $p$, $q$, and $pq$ have to end in $3$, $7$ and $9$ in some order. We see that $3 \cdot 7 \not\equiv 9 \pmod {10}$, but $3 \cdot 9 \equiv 7 \pmod {10}$ and $7 \cdot 9 \equiv 3 \pmod {10}$, so the only restriction is that either $p$ or $q$ ends in $9$ and the other ends in $3$ or $7$. The smallest prime that ends in $9$ is $19$. But note that $2 \cdot 5 \cdot 13 \cdot 19 > 2016$, so the prime that ends in $3$ or $7$ must be either $3$ or $7$. If $p = 3$, then $q$ must be at most $\bigg\lfloor \frac{2016}{2 \cdot 5 \cdot 3} \bigg\rfloor = 67$. There are three primes that work here ($19$, $29$, and $59$). If $p = 7$, then $q$ must be at most $\bigg\lfloor \frac{2016}{2 \cdot 5 \cdot 7}\bigg\rfloor = 28$. There is only one prime that works here ($19$). Therefore in total, there are $\boxed{5}$ northern numbers smaller than $2016$ with the fewest number of divisors possible ($270$, $570$, $870$, $1330$, and $1770$). ¡Olé!