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?
 A: This is false: $4^4$ divides $10^{10}$ but $4$ does not divide $10$.
A: 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).
A: Here is another example taken from this link $$4^{4} \mid 14^{14} \quad \text{but} \ 4 \nmid 14$$
A: 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? 
A: 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)$
