# A number theory puzzle

I recently came across the following number theoretic puzzle. Suppose I've infinitely many cards, each with a natural number written on it. Given any $n\in \mathbb N$, the number of cards which have a divisor of $n$ written is exactly equal to $n$. I need to show that every natural number appears on at least one card. Any ideas on how to proceed?

• I deleted my comment (because I didn't initially understand the question), but it still stands ($n = 1$ is always going to be a problem)...it must be removed, yes? – Jared Oct 4 '14 at 6:11
• Why is $n=1$ a problem? For $n=1$, since 1 is the only divisor of 1, we can conclude that 1 appears on (at least) 1 card. What's the problem? – adrija Oct 4 '14 at 6:13
• I'm trying to understand your constraint. Given any $n$, say $n = 1$, then the number of cards which have a divisor of $n$, say $n = 1$ (which will be every natural number), will be equal to $n$ (which would be $n = 1$ in this case). – Jared Oct 4 '14 at 6:18
• Here's an example, let's say our set is $\{1,2\}$. Let $n = 1$. The number of cards which have divisors of $1$ are both $1$ and $2$ which means the number of cards which have divisor equal to $n = 1$ is $2 \neq 1$. What am I missing here (I'm sure it's something). – Jared Oct 4 '14 at 6:25
• Suppose $n=1$. 1 is the only divisor, so 1 appears on exactly 1 card. Please ignore the bracketed at least in my previous comment. 1 appears on exactly 1 card. For any other $n$, say $n=10$, note that 10 has the divisors 1,2,5 and 10. So, 1,2,5 and 10 together appear on 10 cards. For a prime $n$, say $n=5$, there are 2 divisors and 1 appears on exactly 1 card. So 5 (and actually, any prime $p$) appears on 4 ($p-1)$ cards. Now what? – adrija Oct 4 '14 at 6:25

You're looking for a function $f:\mathbb{N}\to\mathbb{N}$ such that $\sum_{d\mid n} f(d) = n$ for all $n$.

The key is that this determines $f(n)$ if you know $f(1), f(2), \ldots ,f(n-1)$ already. So if you can find any $g$ that does the job, then $f=g$ follows from induction. How to find such a function?

Hint #1: In a cyclic group with $n$ elements, how many elements of order $d$ are there?

Hint #2: How many $n$-th roots of unity are there? How many of those are primitive $d$-th roots of unity?

• Stated as in the first line, one can directly appeal to the Mobius Inversion formula to find $f(d)$. (Though that feels a bit like using a crane to crush a fly.) – Semiclassical Oct 4 '14 at 6:26
• Doesn't the totient function fit the bill? – adrija Oct 4 '14 at 6:27
• Yes, definitely :D. – user71641 Oct 4 '14 at 6:28
• Got it, thanks. This $was$ easy, it seems. Just needed to prove the uniqueness part. – adrija Oct 4 '14 at 6:29
• @Semiclassical You can, but how to show that the result is always positive? – Slade Oct 4 '14 at 6:30

I came up with the following formulae, not sure if they are entirely correct: If i and p (here p is a prime and i is any integer) are coprime then #(ip) = (p-1).#i Else, #(ip) = p.#i

Where, #k represents the number of cards with number k written on them. For example, #(1) = 1, #(2) = 1 (in general for a prime q, #q = q-1)

Now assume that k is the smallest of the numbers that are absent on the cards. Basically we assume that for all i < k, #i>0. Now, there are three options for k: 1. k is a prime, in which case, #k = k-1 > 0; or 2. k is of the form, k = ip (p is a prime) where: 2a. i and p are coprime. Then, #k = (p-1).#i > 0; or 2b. p divides i. Then, #k = p.#i > 0; or 3. k= 1, where obviously #k = 1 > 0

Since in each case we have a contradiction, our assumption was invalid which means all integers are present at least once.

• Welcome to MSE. Please use MathJax to format your answer. – user507623 Feb 18 '18 at 22:03