I am doing a review assignment and I'm stuck on this problem.

a) How many positive divisors does $a$ have? I got $60$

b) How many positive integers less than $a$ are relatively prime to $a$? I got $720$

c) What is the smallest positive integer $m$ such that $a^2m$ is a cube?

d) list all positive divisors $b$ of a for which a divides $b^2$ is also true.

Any help and advice would be greatly appreciated. Thank you for your time and help!

  • 1
    $\begingroup$ I would suggest writing an algorithm (in something like Python) which will spit out all of this information if you plug in any number for $a$. $\endgroup$ – Forever Mozart Dec 10 '14 at 19:55

First, note that $43120 = 2^\color{red}{4}\cdot 5^\color{blue}{1}\cdot 7^\color{green}{2}\cdot 11^\color{purple}{1}$.

Part A

The number of positive integer divisors is the product of one plus each exponent in the prime factorization. That is, $$d(43120) = \color{red}{(4+1)}\color{blue}{(1+1)}\color{green}{(2+1)}\color{purple}{(1+1)} = (5)(2)(3)(2) = 60$$

Part B

The number of positive integers coprime to $43120$ can be found using Euler's Totient function, $\phi(n)$. Since $\phi$ is multiplicative for coprime integers:

$$\phi(43120) = \phi(2^4)\phi(5)\phi(7^2)\phi(11)$$

Also, $\phi(p^n) = p^{n-1}(p-1)$ for prime integers $p$. Then:

$$\begin{align}\phi(43120) &= \left[2^3(2-1)\right]\left[5-1\right]\left[7^1(7-1)\right]\left[11-1\right]\\ &= 8\cdot4\cdot 42\cdot 10\\ &= 13440 \end{align}$$

Part C We want all exponents of $a^2$ to be multiples of three, and we want the smallest such exponents. $$\left(2^\color{red}{4}\cdot 5^\color{blue}{1}\cdot 7^\color{green}{2}\cdot 11^\color{purple}{1}\right)^2 = 2^\color{red}{8}\cdot 5^\color{blue}{2}\cdot 7^\color{green}{4}\cdot 11^\color{purple}{2}$$ Well, it is easy to see that we need to add $1$ to the first exponent, $1$ to the second, $2$ to the third and $1$ to the fourth. Thus, our integer $m$ is: $$m= 2^\color{red}{1}\cdot 5^\color{blue}{1}\cdot 7^\color{green}{2}\cdot 11^\color{purple}{1}$$

Part D This is a similar exponent-related trick as in part c if I'm thinking it through correctly. I'll leave this one as an exercise to the reader. :)

  • $\begingroup$ You are awesome! Thank you, it was much easier with your explanations. $\endgroup$ – Murray Dec 10 '14 at 20:24
  • $\begingroup$ The answer for item d is $2^a\cdot 5\cdot 7^b\cdot 11$, with $a=2,3$ or $4$ and $c=1$ or $2$ (and so there are six such numbers)? $\endgroup$ – Larara Dec 11 '14 at 3:49

First, we factor $$43120=2^45^17^211^1$$

Solutions to a, c, d, are obtained from the exponents $u=(4,1,2,1)$.

a) A positive divisor is a $4$-vector of nonnegative integers majorized by $u$. That is $$\{(a,b,c,d):0\le a\le 4, 0\le b\le 1, 0\le c\le 2, 0\le d\le 1\}$$ There are $(4+1)\times(1+1)\times (2+1)\times (1+1)=60$ positive divisors.

c) $a^2$ corresponds to $(8,2,4,2)$. To make a cube, each must be a multiple of $3$, i.e. $(9,3,6,3)$. Subtracting, we get $(1,1,2,1)$, i.e. $2^15^17^211^1=m$.

d) For $a$ to divide $b^2$, $u$ must be majorized by the $4$-vector of $b^2$. For example, if $b$ corresponds to $(5,1,2,2)$, then $b^2$ corresponds to $(10,2,4,4)$, which majorizes $u$, since it is larger in each component. I leave to you to count how many there are of these.

b) You seek $\phi(43120)$, the Euler totient. This is multiplicative, so you want $\phi(2^4)\phi(5)\phi(7^2)\phi(11)$.

  • $\begingroup$ +1. For the OP, to compute the factorization, it might help to observe that $a = 43120 = 40320+2800 = 8!+4*7*100$. Then $a = (1)(2)(3)(2^2)(5)(2*3)(7)(2^3)+(2^2)(7)(2^2*5^2) = (2^4)(5)(7)(2^3*3^2+5) = (2^4)(5)(7)(77) = (2^4)(5)(7^2)(11)$. $\endgroup$ – Alex Wertheim Dec 10 '14 at 20:03
  • $\begingroup$ Sure. Or just trial division by small primes, there are many ways. I did it with wolfram alpha. $\endgroup$ – vadim123 Dec 10 '14 at 20:05
  • $\begingroup$ You guys are so quick to help! Thank you so much! $\endgroup$ – Murray Dec 10 '14 at 20:24

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.