# 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

## 5 Answers

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\:.\:$ Hence we conclude that $\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 that employed above. 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\$ (Chandru's link). $\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

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 - –  mixedmath 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$$

-