Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
show 4 more comments

5 Answers

up vote 38 down vote accepted

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

share|improve this answer
LOL! "Someone" had decided after close to 3 years of careful study that this answer is "not helpful". May be I should have spelled it out that non-squarefree values of $n$ may cause a problem rather than assuming that all the readers realize this upon reading my bit. For the record: I have the habit of upvoting the competing answers, and did so here because 1) they are all good. 2) it is bad sportmanship not to. –  Jyrki Lahtonen 2 days ago
add comment

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

share|improve this answer
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
add comment

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?

share|improve this answer
+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
add comment

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

share|improve this answer
Wow, that's pretty thorough. Many thanks! –  Carolus Jul 27 '11 at 17:14
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.