Suppose $a$, $b$, $c$, and $d$ are distinct positive integers such that $a^b$ divides $b^c$, $b^c$ divides $c^d$, and $c^d$ divides $d^a$. (a) Is it possible to determine which of the numbers $a$, $b$, $c$, $d$ is the smallest? (b) Is it possible to determine which of the numbers $a$, $b$, $c$, $d$ is the largest?
Problem
Source: XIX OlimpĂada Matemática Rioplatense (2010)
Tags: inequalities, number theory, number theory unsolved
Binomial-theorem
22.10.2011 22:11
$a^b|b^c|c^d|d^a$ is given.
Lemma 1: $a^b|b^c\implies$ $a > b<c$ or $c<b> a$, besides for when $a|b$ or $b|a$.
Proof: This is directly true from $\gcd(a^b, b^c)=\gcd(a,b)^{\min \{b,c\}}\forall a\cancel{|} b, b\cancel{|} a$, which is an extension to a Lemma in Problems of Number Theory in Mathematical Competitions
Proof of this: Let $\gcd(a,b)=m$ for some integer $m$. Hence, we get $m|a$ and $m|b$. Let $a=km$ and $b=lm$ for some integers $k$ and $l$. Note that $\gcd(k,l)=1$, because if $\gcd(k, l)\neq 1$, then we would have $\gcd(a,b)>m$. Now note that $\gcd(a^b, b^c)=\gcd((km)^b, (lm)^c))=m^{\min(b,c)}\gcd(k^b, l^c)$, which can be found using the lemma $\gcd(ad, bd)=d\gcd(a,b)$ from Problems of Number Theory in Mathematical Competitions . From here, use the third and final Lemma from Problems of Number Theory in Mathematical Competitions, which is $\gcd(k,l)=1\implies \gcd(k^b, l^c)=1$, which can be proven by noting that if $k$ and $l$ share no common divisors, then continuing to multiply the numbers won't result in having any common divisors. Hence, $\gcd(k^b, l^c)=1$, and we get $\gcd(a,b)=\gcd((km)^b, (lm)^c))=m^{\min(b,c)}$.
Note that this equation does not hold true for when $a|b$ or when $b|a$, because, for example when we have $a=kb$ for some $k$, we have $\gcd(kb, b)=b\gcd(k,1)=b$. Now note that $\gcd(a,b)^{\min(b,c)}$ is not necessarily going to be equal to $b$, because we would have to have $\min(b,c)=1$ for this to be true. $\Box$.
Hence since we want $\gcd(a^b, b^c)=a^b$, hence we have $\gcd(a,b)^{\min \{b,c\}}=a^b$. Make the observation that when $b<c$, we have $\gcd(a,b)^{b}=a^b\implies \gcd(a,b)=a\implies a|a$ and $b|a$, hence $a\ge b<c$. When $b>c$, we have $\gcd(a,b)^{c}=a^b$, which implies that $a| \gcd(a,b)$. This is true $\iff a|b$, hence we have $c<b\ge a$ in this case. Since $b\neq a$, we must have $c<b>a$ in the second case, and $a> b< c$ in the first case.
Lemma 2: $b^c|c^d \implies$ $b> c<d$ or $d< c >b$, besides for when $b|c$ or $c|b$
Proof: There are no restrictions on $a,b,c$ from Lemma 1, besides for $a\cancel{|}b$ and $b\cancel{|}a$, that do not apply here, hence from Lemma 1, this is true.
Lemma 3: Further note that $c^d|d^a$ implies $c>d<a$ or $a<d>c$, besides for when $c|d$ or $d|c$.
Proof: Lemma 2
Note that inequality $c>d<a$ from Lemma 3 is satisfied $\iff d<c>b$ from Lemma 2, which is true $\iff a>b<c$ from Lemma 1. From this, we have $a>b, c>b, c>d, a>d$. Hence, we know that $a$ and $c$ are greater than $b$ and $d$ respectively in this case, but we don't have any comparison between $a$ and $c$.
Now, note that if we use the inequality $a<d>c$ from Lemma 3, we have to have $b>c<d$ from Lemma 2, and we must have $c<b>a$ from Lemma 1. Hence, we have $d>a, d>c, b>c, b>a$, hence we must have $d$ and $b$ being greater than both $c$ and $a$, but we have no comparison between $d$ and $b$ and $c$ and $a$ respectfully.
Because in both case 1 and case 2, we can't determine the maximum and minimum of $a,b,c,d$, it is impossible to find the maximum/minimum of $a,b,c,d$ for this case.
We now account for when $a|b$ or $b|a$, and $b|c$ or $c|b$, and $c|d$ or $d|c$.
Note that it is impossible to determine which number is greatest/smallest in this case, because $a|b$ implies that $b>a$ (because $b\neq a$), and $b|a$ implies that $a>b$. Creating all the inequalities gives us:
$b>a \text{ or } a>b$
$c>b \text{ or} b>c$
$d>c \text{ or } c>d$
From these inequalities, we can find that $b$ can be the maximum, (with case 1, 2, 2), $c$ could be the maximum (cases 1, 1, 2), $a$ could be the maximum (cases 2,2,2), or $d$ could be the maximum (cases 1,1, 1).
Also, we could have $a$ being the minimum (1, 1, 1), $b$ being the minimum (cases 2, 1, 1), $c$ being the minimum (cases 2, 2, 1), or $d$ being the minimum (cases 2, 2,2).
Because in both cases that we have, and we have proven it is impossible to find the maximum/minimum in both cases, we are done $\Box$
Remark: Thanks a lot to Problems of Number Theory in Mathematical Competitions for the Lemma used in Lemma 1, which I extended to use in Lemma 1. Also, thanks to my dad for some help on this problem (mainly the case 2 inequalities). Remark 2: Changed some things in solution, some recommended by dragon96/realized something was incorrect.
littletush
04.12.2011 07:08
I will give an example for (2),and (1) is analogous. for a max:$a=p^{t+3},b=p^t,c=p^{t+1},d=p^{t+2}$; for d max:$a=p^{t-1},b=p,c=p^{\frac{t}{p}},d=p^t$ where p is a prime,t sufficiently large.