# Proper Divisors / Number Theory

Let $g(n)$ be the product of the proper positive integer divisors of $n$. (Recall that a proper divisor of $n$ is a divisor other than $n$.) For how many values of $n$ does $n$ not divide $g(n)$, given that $2 \le n \le 50$?

I'm aware of the terminology regarding proper divisors. However, I was not able to crack this problem in under 10 minutes.

Thought Process 1: Find all primes between 2 and 50. However, this returned the wrong answer.

Thought Process 2: I thought of brute forcing the answer, but that seemed too long.

Finally, I ended up getting an answer (which was correct), but I needed a faster way. Does anyone know a way to get the answer (in under 10 minutes)?

• Primes and squares of primes seem to be the only cases where $n$ does not divide $g(n)$. I’ll give an answer in a moment. – user328442 Nov 22 '17 at 17:58
• You could use $n g(n)=n^{d(n)/2}$ where $d(n)$ is the number of divisors of $n$. – Angina Seng Nov 22 '17 at 18:01

## 4 Answers

Given a number $2\leq n\leq 50$ with prime decomposition $$n = 2^{e_2}\cdot3^{e_3}\cdots47^{e_{47}}$$ the number of divisors of $n$, including $n$ and $1$, is $$\sigma(n) = (1+e_2)(1+e_3)\cdots(1+e_{47})$$ Note that if there are two or three divisors according to this count, then $n$ is not divisible by the product of its proper divisors, because that product will be $1$ in the case of two divisors, and $\sqrt n$ in the case of three divisors (if there are three divisors, then $n$ is necessarily the square of a prime number, because exactly one of the exponents above is $3$, and the rest are $1$).

Now, on the other hand, if there are four or more divisors, then there is at least one proper divisor that is neither $1$ nor $\sqrt n$. Call that divisor $m$. Both $m$ and $\frac mn$ are proper divisors of $n$, they are distinct, and their product equals $n$. So they both appear as factors of $g(n)$, which means that $g(n)$ is divisible by $n$.

Therefore you are looking for primes and squares of primes.

• To clarify, the answer would be 19. – A Piercing Arrow Nov 22 '17 at 18:04
• @Skupp That makes sense. 15 primes and 4 squares. – Arthur Nov 22 '17 at 18:06

We are looking for integers $n$ between $2$ and $50$, inclusively, such that $g(n)$ does not divide $n$.

Let’s take a look at a few cases.

1. Suppose that $n$ is prime. The only proper divisor must be $1$ and so $g(n) = 1$ which means that $n$ cannot divide $g(n)$.

2. Suppose that $n$ is the square of a prime. Then there is some prime $p$ such that $n = p^2$ and so $g(n) = p$. Thus, $n$ cannot divide $g(n)$.

3. Suppose that $n$ is the product of 2 distinct primes, say $p$ and $q$. Then $g(n) = pq$ and so $n$ divides $g(n)$. Note: we can generalize this to any number of distinct primes as long as there is more than $1$.

4. Suppose that $n$ is the product of the square of a prime and a different prime. Say, $n = p^2q.$ Then $g(n) = p^3q = pn.$ Note: we can generalize from here but I leave that to you.

This means that we need only count primes and prime squares between $2$ and $50$, inclusively.

So, we can quickly count $19$ such integers.

Namely, $\{4, 9, 25, 49\}$ (because counting the prime squares is relatively quick) and $\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}$. Note that for a reasonably small number like $50$, counting primes is somewhat quick since we need only list $2$ then check odd integers, most of which should be known to be prime or composite based on sight to many of us.

The grand total is $19$.

If $a$ and $b$ are two different divisors of $n$, then $ab\mid g(n)$, so if $n=ab$ with $1\lt a\lt b\lt n$, then $n\mid g(n)$. Thus the only possible $n$'s that don't divide $g(n)$ are primes and squares of primes. Since $g(p)=1$ and $g(p^2)=p$ when $p$ is prime, we need only count the size of the set $\{2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49\}$. I get $19$.

If $n$ is not a prime and not the square of a prime, then it has a proper divisor $d$ such that $n/d$ is $\neq d$ and hence another proper divisor. Hence $n = d \cdot n/d$ divides $g(n)$.