# How do we prove $n^n \mid m^m \Rightarrow n \mid m$?

I'm not sure I've got this right. When proving $a^n \mid b^n \Rightarrow a \mid b$, can we do this indirectly? In short,

"Suppose $a$ does not divide $b$, this implies that $a^n$ does not divide $b^n$. But $a^n \mid b^n$, hence $a$ divides $b$."

How about $n^n \mid m^m \Rightarrow n \mid m$? Can we do this the same way?

• For $a$, $b$, direct is clear, once you have the Unique Factorization Theorem. – André Nicolas Jul 20 '11 at 6:51
• +1 This is a cute problem. At first I wanted to prove it using unique factorization, but the inequalities between multiplicities of a prime factor never worked out right. Then I realized that it is wrong :-) – Jyrki Lahtonen Jul 20 '11 at 6:56
• @André: Ok, I guess I should have thought of that :/ But it's not wrong to do it indirectly, right? – Carolus Jul 20 '11 at 7:12
• @Carolus: If I were a teacher grading your solution as an answer to an exam problem, I might want to see a justification for your step: "If $a$ does not divide $b$, then $a^n$ does not divide $b^n$." If that implication had been proven in the book/lecture notes, or as an example, I might let it slide. But if that bit had not been covered earlier, then you need to prove that it is ok. That step is valid, but in such a setting, you should be able to justify it somehow. So to answer the question in your comment to André: "It depends." – Jyrki Lahtonen Jul 20 '11 at 7:32
• @Carolus: Indirect would be fine, of course, but if it is an exercise, detail is needed in any case. After a certain level, it is enough to say "By the Unique $\dots$" since the reader can presumably fill in the details. So if you are in $4$-th year Math, you can be brief. If this is your first "proof" course, much more detail would be expected. – André Nicolas Jul 20 '11 at 8:05

This is false: $4^4$ divides $10^{10}$ but $4$ does not divide $10$.

No, your second implication holds only for squarefree $$\rm\:n,\:$$ namely

Theorem $$\rm\quad n\in\mathbb N\:$$ is squarefree $$\rm\, \iff\, \forall\ m\in \!\mathbb N\!:\, n^n\: |\: m^{\:m} \Rightarrow\ n\:|\:m$$

Proof $$\ (\Rightarrow)\ \$$ If $$\rm\:n\:$$ is squarefree then prime $$\rm\:p\:|\:n\:|\:n^n\:|\:m^m\ \Rightarrow\ p\:|\:m\:.\:$$ So we conclude $$\rm n\:|\: m\$$ since $$\rm\:m\:$$ is divisible by each prime factor of $$\rm\:n,\:$$ so also by their $$\rm\:lcm =\:$$ product $$\rm = n.$$

$$(\Leftarrow)\$$ $$\rm\ n\,$$ not squarefree $$\rm\:\Rightarrow n = a\, p^k,\:$$ prime $$\rm\:p\nmid a,\ k\ge 2\:.\:$$ Let $$\rm\: j\in\mathbb N,\ p^{k-1}\!\nmid j\:,\:$$ e.g. $$\rm\ j = 1$$

Then $$\rm\displaystyle\:\ m\: =\: k\:n+a\:p\;j\ \Rightarrow\ n^n =\: (a\:p^k)^n\ |\ (a\:p)^{k\:n}\ | \ m^m\ \:$$ by $$\rm\:\ ap\ |\ m \ge k\:n$$

but $$\rm\ n\nmid m,\$$ else $$\rm\displaystyle\ n\:|\:a\:p\:j\ \Rightarrow\: p^{k-1}\:|\ j\:,\:$$ contra choice of $$\rm\ j$$.

Remark $$\$$ The counterexamples in the other answers are special cases of this:

E.g. $$\rm\ k = 2,\ a = 1\$$ yields $$\rm\: m = k\:n + a\:p\:j = 2\:n + p\:j\:,\ p\nmid j\:.\:$$

Hence $$\rm\:n = 4\:,\ p = 2\$$ yields $$\rm\:m = 8 + 2\:j\:,\ 2\nmid j\:.\:$$ So $$\rm\: j= 1\:$$ yields $$\rm\:m = 10\$$ (Jyrki);

$$\rm\, j = 3\:$$ yields $$\rm\:m = 14\$$ (link from Chandru = user9413).

$$\rm\ n = a\:p^k = 3\cdot 2^2$$ yields $$\rm\:m = k\:n + a\:p\:j = 24 + 6\:j,\ 2\nmid j\:.\:$$ So $$\rm\:j = 7\:\Rightarrow\:m = 66\:$$ (mixedmath).

• Great answer, as it shows not only why the argument doesn't work but also where it can work. – Ross Millikan Jul 21 '11 at 5:34
• this can be the best answer – Dinesh Jul 25 '11 at 18:10
• It is true for squarefree $n$ and there are counterexamples for all non-squarefree $n$. But which $m$ is it true for? For example $m=1$ or prime or a prime power or I think $m=6$ or $m=15$ or other products of two close primes. Which more are there? – Henry Jan 15 '17 at 13:40

Not quite. And here's why:

Note that $12 \not | \;66$. Also, $12 = 2^2 \cdot 3$ and $66 = 2 \cdot 3 \cdot 11$. But $12^{12} |\; 66^{66}$, because $66^{66}$ has 66 'different' factors of 2 and 66 'different' factors of 3, and $12^{12}$ has only 24 'different factors of 2 and 12 factors of 3.

So the fact that $a \not | \;\;b$ does not imply that $a^a \not |\; \; b^b$. And I think that was the content of your question, right?

• +1: Folks, thank you for your support, but I'm upvoting this. We were separated by only a handful of seconds, and I had less to type :-) – Jyrki Lahtonen Jul 20 '11 at 12:46
• @Jyrki: ah, well to the victor go the spoils. ;p Thank you - – davidlowryduda Jul 20 '11 at 16:24

Below are equivalent definitions of $\rm\ q\,$ squarefree. Yours is $(5)$.

Theorem $\$ Let $\rm\ 0 \ne q\in \mathbb Z\:.\ \$ The following are equivalent.

$(1)\rm\quad\ \ \ \, n^2\,|\ q\ \ \Rightarrow\ \ n\ |\ 1\qquad\$ for all $\rm\:\ n\in \mathbb Z$

$(2)\rm\quad\ \ \ \, n^2\, |\, qm^2 \!\Rightarrow n\ |\ m\qquad\!$ for all $\rm\: \ n,m\in \mathbb Z$

$(3)\rm\qquad\ q\ |\ n^2\ \Rightarrow\ q\ |\ n\qquad\$ for all $\rm\:\ n\in \mathbb Z$

$(4)\rm\qquad\ q\ |\ n^k\ \Rightarrow\ q\ |\ n\qquad\$ for all $\rm\:\ n\in \mathbb Z,\ k\in \mathbb N$

$(5)\rm\quad\:\ \: q^q\ |\ n^n\ \Rightarrow\ q\ |\ n\qquad\$ for all $\rm\:\ n\in \mathbb N,\$ for $\rm\ q > 0$

Proof $\ \: (1\Rightarrow 2)\rm\:\ \$ Canceling $\rm\:(n,m)^2\:$ from LHS of $(2)\:$ we may assume w.l.o.g. that $\rm\:(n,m)\:=\:1.\$ By  Euclid's Lemma $\rm\: n^2\, |\, qm^2\: \Rightarrow\ n^2\: |\: q\ \Rightarrow\ n\:|\:1\ \Rightarrow\ n\:|\:m$

$(2\Rightarrow 3)\rm\quad q\ |\ n^2\ \Rightarrow\ q^2\ |\ qn^2\ \Rightarrow\ q\ |\ n$

$(3\Rightarrow 4)\rm\quad k \ge 2\ \Rightarrow\ k \le 2\:(k-1)\$ so $\rm\:\ q\ |\ n^k\ |\ (n^{k-1})^2\ \Rightarrow\ q\ |\ n^{k-1}\:\ldots\:\Rightarrow\ q\ |\ n$

$(4\Rightarrow 5)\rm\quad q\ |\ q^q\ |\ n^n\ \Rightarrow\ q\ |\ n$

$(5\Rightarrow 1)\:$ via $\:\lnot\: 1\Rightarrow\lnot\: 5.\$ By $\rm\:\lnot 1,\,\ q\: =\: ab^2,\:\ b\nmid 1.\:$ Put $\rm\ n = abc\:$ for $\rm\:c\:$ as below.

$\rm\qquad\ \ \ q\ |\ (ab)^2\ \Rightarrow\ q^{\:q}\ |\ (ab)^{2\:q}\ |\ (abc)^{abc}\! = n^n\quad\ \ for\ all \:\ c\:\ with\ \ abc > 2\:q$

Since $\rm\ b\nmid 1\ \Rightarrow\ q\nmid ab,\:$ we may choose $\rm\:c\:$ so that also $\rm\ q\nmid abc,\$ e.g. $\rm\:\ c\equiv 1\,\ (mod\ q)$

• Wow, that's pretty thorough. Many thanks! – Carolus Jul 27 '11 at 17:14

Here is another example taken from this link $$4^{4} \mid 14^{14} \quad \text{but} \ 4 \nmid 14$$