23
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For $a$, $b$, direct is clear, once you have the Unique Factorization Theorem. $\endgroup$ – André Nicolas Jul 20 '11 at 6:51
  • 3
    $\begingroup$ +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 :-) $\endgroup$ – Jyrki Lahtonen Jul 20 '11 at 6:56
  • $\begingroup$ @André: Ok, I guess I should have thought of that :/ But it's not wrong to do it indirectly, right? $\endgroup$ – Carolus Jul 20 '11 at 7:12
  • 2
    $\begingroup$ @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." $\endgroup$ – Jyrki Lahtonen Jul 20 '11 at 7:32
  • 1
    $\begingroup$ @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. $\endgroup$ – André Nicolas Jul 20 '11 at 8:05
63
$\begingroup$

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

$\endgroup$
53
$\begingroup$

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\ $ (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).

$\endgroup$
  • 8
    $\begingroup$ Great answer, as it shows not only why the argument doesn't work but also where it can work. $\endgroup$ – Ross Millikan Jul 21 '11 at 5:34
  • 2
    $\begingroup$ this can be the best answer $\endgroup$ – Dinesh Jul 25 '11 at 18:10
  • 2
    $\begingroup$ 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? $\endgroup$ – Henry Jan 15 '17 at 13:40
19
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Wow, that's pretty thorough. Many thanks! $\endgroup$ – Carolus Jul 27 '11 at 17:14
18
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ +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 :-) $\endgroup$ – Jyrki Lahtonen Jul 20 '11 at 12:46
  • 1
    $\begingroup$ @Jyrki: ah, well to the victor go the spoils. ;p Thank you - $\endgroup$ – davidlowryduda Jul 20 '11 at 16:24
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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