2
$\begingroup$

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)?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – user328442 Nov 22 '17 at 17:58
  • 1
    $\begingroup$ You could use $n g(n)=n^{d(n)/2}$ where $d(n)$ is the number of divisors of $n$. $\endgroup$ – Angina Seng Nov 22 '17 at 18:01
2
$\begingroup$

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.

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

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

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.