Let $ X$, $ Y$, $ Z$ be distinct positive integers having exactly two digits in such a way that: $ X=10a +b$ $ Y=10b +c$ $ Z=10c +a$ ($ a,b,c$ are digits) Find all posible values of $ gcd(X,Y,Z)$
Problem
Source: Argentina IMO TST 2007 problem 1
Tags: number theory, greatest common divisor, algebra unsolved, algebra
28.08.2009 11:11
lambruscokid wrote: Let $ X$, $ Y$, $ Z$ be distinct positive integers having exactly two digits in such a way that: $ X = 10a + b$ $ Y = 10b + c$ $ Z = 10c + a$ ($ a,b,c$ are digits) Find all posible values of $ gcd(X,Y,Z)$ $ 11$ does not divide $ \gcd(X,Y,Z)$, else we would have $ a=b=c$ and $ X=Y=Z$ $ \gcd(X,Y,Z)|(X+Y+Z)=11(a+b+c)$ and so $ \gcd(X,Y,Z)|(a+b+c)$ and so $ \gcd(X,Y,Z)\leq 26$ $ 5$ does not divide $ \gcd(X,Y,Z)$, else we would have $ a=b=c=5$ and $ X=Y=Z$ $ 6$ does not divide $ \gcd(X,Y,Z)$, else we would have $ a,b,c$ even with pairwaise sums all equal to $ 6$ or $ 12$, which is impossible $ 9$ does not divide $ \gcd(X,Y,Z)$, else we would have $ (a,b,c)\in\{(0,0,0),(9,9,9)\}$ So $ \gcd(X,Y,Z)\in\{1,2,3,4,7,8,13,14,16,17,19,21,23,26\}$, so just $ 14$ tests : $ \gcd(11,12,21)=1$ $ \gcd(22,24,42)=2$ $ \gcd(33,39,93)=3$ $ \gcd(44,48,84)=4$ $ \gcd(14,49,91)=7$ $ \gcd(X,Y,Z)=8$ $ \implies$ $ a,b,c$ all even and so $ X,Y,Z\in\{24,48,64,88\}$ so no solution. $ \gcd(13,39,91)=13$ $ \gcd(28,84,42)=14$ $ \gcd(X,Y,Z)=16$ $ \implies$ $ a,b,c$ all even and so $ X,Y,Z\in\{48,64\}$ so no solution. $ \gcd(X,Y,Z)=17$ $ \implies$ $ X,Y,Z\in\{17,34,51,68,85\}$ so no solution. $ \gcd(X,Y,Z)=19$ $ \implies$ $ X,Y,Z\in\{19,38,57,76,95\}$ so no solution. $ \gcd(X,Y,Z)=21$ $ \implies$ $ X,Y,Z\in\{21,42,63,84\}$ so no solution. $ \gcd(X,Y,Z)=23$ $ \implies$ $ X,Y,Z\in\{23,46,69,92\}$ so no solution. $ \gcd(X,Y,Z)=26$ $ \implies$ $ X,Y,Z\in\{26,52,78\}$ so no solution. Hence the answer : $ \gcd(X,Y,Z)\in\{1,2,3,4,7,13,14\}$ I hope there exists a more interesting solution ...
28.08.2009 11:45
I've got a slightly different solution, but I wouldn't say it's interesting. We have $ \gcd(X$, $ Y$, $ Z) \mid \alpha X + \beta Y + \gamma Z$ for some integers $ \alpha$, $ \beta$, $ \gamma$. Choosing $ ( \alpha$, $ \beta$, $ \gamma) = (1$, $ 1$, $ 1)$ one gets $ \gcd(X$, $ Y$, $ Z) \mid 11(a + b + c)$ and hence $ \gcd(X$, $ Y$, $ Z) \mid a + b + c \le 26$, as $ \gcd(X$, $ Y$, $ Z) \mid 11$ would lead to $ a = b = c$, a contradiction. Moreover, choosing $ ( \alpha$, $ \beta$, $ \gamma) = (1$, $ 100$, $ - 10)$, one gets $ \gcd(X$, $ Y$, $ Z) \mid 1001b = 7 \cdot 11 \cdot 13b$ and hence $ \gcd(X$, $ Y$, $ Z) \mid 7 \cdot 13 b$ and the same for $ a$ and $ c$. But now we can rule out some cases, because one of the numbers $ 5$, $ 6$, $ 8$, $ 9$ can't divide $ a$, $ b$, $ c$ simultaneously. Thus, $ \gcd(X$, $ Y$, $ Z) \mid l \cdot 7 \cdot 13$, where $ l \in \{1$, $ 2$, $ 3$, $ 4$, $ 7\}$. Hence $ \gcd \in \{ 1$, $ 2$, $ 3$, $ 4$, $ 7$, $ 13$, $ 14$, $ 21$, $ 26 \}$ and each of these values, except $ 21$ and $ 26$, gives a solution indeed. Hence the anser is: $ \gcd(X$, $ Y$, $ Z) \in \{ 1$, $ 2$, $ 3$, $ 4$, $ 7$, $ 13$, $ 14 \}$.
28.08.2009 12:06
FelixD wrote: ... But now we can rule out some cases, because $ a$, $ b$, $ c$ can't divide one of the numbers $ 5$, $ 6$, $ 8$, $ 9$ simultaneously. Thus, $ \gcd(X$, $ Y$, $ Z) \mid l \cdot 7 \cdot 13$, where $ l \in \{1$, $ 2$, $ 3$, $ 4$, $ 7\}$. ... You mean one of $ 5,6,7,8,9$ can't divide $ a,b,c$ simultainiously otherwise $ a = b = c$. Thus, $ \gcd(X$, $ Y$, $ Z) \mid l \cdot 7 \cdot 13$, where $ l \in \{1, 2, 3, 4\}$.
28.08.2009 12:17
Rafikafi wrote: FelixD wrote: ... But now we can rule out some cases, because $ a$, $ b$, $ c$ can't divide one of the numbers $ 5$, $ 6$, $ 8$, $ 9$ simultaneously. Thus, $ \gcd(X$, $ Y$, $ Z) \mid l \cdot 7 \cdot 13$, where $ l \in \{1$, $ 2$, $ 3$, $ 4$, $ 7\}$. ... You mean one of $ 5,6,7,8,9$ can't divide $ a,b,c$ simultainiously otherwise $ a = b = c$. Thus, $ \gcd(X$, $ Y$, $ Z) \mid l \cdot 7 \cdot 13$, where $ l \in \{1, 2, 3, 4\}$. Of course I mean $ 5$, $ 6$, $ 8$, $ 9$ can't divide $ a$, $ b$, $ c$ simultaneously. But cou can't rule out the $ 7$ IMHO, because we already have $ \gcd \mid 7 \cdot 13l$.
28.08.2009 12:38
Yes you can but at this example it doesn't matter. $ l$ is nothing else than $ gcd(a,b,c)$ If $ l=7 \Rightarrow 7|a$ and $ b$ and $ c$ Therefore $ a=b=c=7$ This doesn't mean that $ 7$ cannot divide $ gcd(X,Y,Z)$ it only means that $ 49$ doesn't divide $ gcd(X,Y,Z)$