IX CPS - Zadanie 5

Liczby całkowite dodatnie $a_1,a_2,\dots,a_n$ spełniają następujące warunki:

$1\leq a_1<a_2<\dots<a_n\leq50$ ;
dla dowolnych liczb całkowitych dodatnich $b_1,b_2,\dots,b_n$ istnieje taka liczba całkowita dodatnia $m$ oraz liczby całkowite dodatnie $c_1,c_2,\dots,c_n$ , że

$ mb_i=(c_i)^{a_i}\text{ dla }i=1,2,\dots,n. $

Wykazać, że $n\leq16$ oraz wyznaczyć liczbę różnych ciągów $(a_1,a_2,\dots,a_n)$ spełniających powyższe warunki dla $n=16$ .

Rozwiązanie

Zaczniemy od uzasadnienia, że liczby $a_1,\dots,a_n$ są parami względnie pierwsze. Załóżmy, że tak nie jest. Wtedy $\gcd(a_i,a_j)=d>1$ dla pewnych $i\neq j$ . Niech $a_i=u\cdot d$ i $a_j=v\cdot d$ . Na mocy (ii) dla $b_i=1$ i $b_j=2$ istnieją $m$ , $c_i$ i $c_j$ , spełniające warunek

$ m\cdot b_i=c_i^{a_i}\quad\text{i}\quad m\cdot b_j=c_j^{a_j}, \quad\text{lub równoważnie}\quad m=(c_i^u)^d\quad\text{i}\quad 2m=(c_j^v)^d. $

Zatem $2(c_i^u)^d=(c_j^v)^d$ , co jest niemożliwe, bo po rozłożeniu na czynniki pierwsze obu stron tego równania wykładnik 2 w wyrażeniu z lewej strony nie jest podzielny przez $d$ , zaś po prawej stronie 2 występuje z wykładnikiem podzielnym przez $d$ . Otrzymana sprzeczność dowodzi, że $a_1, \dots, a_n$ są względnie pierwsze.

Wykażemy teraz, że dla dowolnych $a_1, \dots, a_n$ , które są parami względnie pierwsze, warunek (ii) jest spełniony. Niech $b_1$ , \dots, $b_n$ będą dowolnymi dodatnimi liczbami całkowitymi, a $\{p_1,\dots,p_k\}$ będzie zbiorem wszystkich dzielników pierwszych liczby $b_1\cdot b_2\cdot\dots\cdot b_n$ . Szukamy liczby $m$ postaci

$ m=p_1^{\alpha_1}\cdot\dots\cdot p_k^{\alpha_k}. $

Dla $i=1,\dots,n$ oznaczmy przez $\beta_{i,j}$ wykładnik przy podstawie $p_j$ w rozkładzie na czynniki pierwsze liczby $b_i$ . Do tego by $m\cdot b_i$ była $a_i$ -tą potęga liczby całkowitej, wystarczy, by $\alpha_j+\beta_{i,j}$ była wielokrotnością $a_i$ , dla $j=1,\dots,k$ . Wystarczy zatem znaleźć $\alpha_j$ spełniające poniższe kongruencje:

$ \alpha_j\equiv-\beta_{1,j}\pmod{a_1},\quad \alpha_j\equiv-\beta_{2,j}\pmod{a_2}, $

$ \dots,\quad\alpha_j\equiv-\beta_{n,j}\pmod{a_n}. $

Istnienie takiego $\alpha_j$ wynika z chińskiego twierdzenia o resztach, ponieważ $a_1, \dots, a_n$ są względnie pierwsze.

Udowodniliśmy, że warunek (ii) jest jest spełniony wtedy i tylko wtedy, gdy liczby $a_1, \dots, a_n$ są parami względnie pierwsze. W zbiorze $\{1,2,\dots,50\}$ jest dokładnie 15 liczb pierwszych. Gdyby $n\geq17$ , wśród liczb $a_2,a_3,\dots,a_n$ znaleźlibyśmy przynajmniej dwie, które mają wspólny dzielnik pierwszy, gdyż $2\leq a_2<a_3<\dots<a_n\leq50$ . Jest to sprzeczne z faktem, że $a_1,\dots,a_n$ są względnie pierwsze, a stąd $n\leq16$ .

Dla $n=16$ , z powyższych rozważań wynika, że $a_1=1$ , zaś $a_2$ , $a_3, \dots, a_{16}$ muszą być potęgami różnych liczb pierwszych. Ze względu na to, że $a_{16}\leq50$ , dopuszczalne potęgi liczb pierwszych $p$ ( $p<50$ ), to: