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?

  • $\begingroup$ 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? $\endgroup$ – Jared Oct 4 '14 at 6:11
  • 2
    $\begingroup$ 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? $\endgroup$ – adrija Oct 4 '14 at 6:13
  • $\begingroup$ 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). $\endgroup$ – Jared Oct 4 '14 at 6:18
  • $\begingroup$ 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). $\endgroup$ – Jared Oct 4 '14 at 6:25
  • $\begingroup$ 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? $\endgroup$ – 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?

  • 1
    $\begingroup$ 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.) $\endgroup$ – Semiclassical Oct 4 '14 at 6:26
  • 2
    $\begingroup$ Doesn't the totient function fit the bill? $\endgroup$ – adrija Oct 4 '14 at 6:27
  • $\begingroup$ Yes, definitely :D. $\endgroup$ – user71641 Oct 4 '14 at 6:28
  • $\begingroup$ Got it, thanks. This $was$ easy, it seems. Just needed to prove the uniqueness part. $\endgroup$ – adrija Oct 4 '14 at 6:29
  • $\begingroup$ @Semiclassical You can, but how to show that the result is always positive? $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.