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?

  • 0
    @Carolus: Let $p$ be$a$prime, and suppose $p$ appears to highest power $p^\alpha$ in $a$, and $p^\beta$ in $b$. (We allow $0$ exponents here, for convenience). We want to show that $\alpha \le beta$. From the condition on $a^n$, $b^n$ we have $n\alpha \le n\beta$. This implies $\alpha \le \beta$. Note by the way that statement of problem should have specified $n$ is$a$*positive* integer. Of course we need not be always endlessly fussy like this. After$a$while, we often *know* when$a$"loosely" put argument can be made bullet-proof. In such cases there is no point in fussing.2011-07-20

5 Answers 5

64

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

54

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

  • 2
    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?2017-01-15
19

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
    @Jyrki: ah, well to the victor go the spoils. ;p Thank you -2011-07-20
19

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

  • 1
    Wow, that's pretty thorough. Many thanks!2011-07-27
5

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