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  
+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
2  
@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
1  
@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 5

up vote 38 down vote accepted

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

share|improve this answer

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
5  
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
1  
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?

share|improve this answer
3  
+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
1  
@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)$

share|improve this answer
1  
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$$

share|improve this answer

Your Answer

 
discard

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.