[Teoria liczb] Siódemka z Teoria liczb

[Elayne]

1.) Udowodnij, że układ
\(\displaystyle{ x^{6}+x^{3}+x^{3}y+y=147^{157},\\
x^{3}+x^{3}y+y^{2}+y+z^{9}=157^{147}}\)
nie ma rozwiązań w liczbach całkowitych x, y, z.

2.) Niech liczby x, y, z należą do zbioru liczb pierwszych, \(\displaystyle{ x<y<z}\) oraz iloczyn
\(\displaystyle{ x \cdot y \cdot z}\) wynosi:

\(\displaystyle{ 4552476622578176510234458991678923047576627539391694340370589958698222\\
7209718089224933768238385980667045356856590320730715919798518398280837\\
6678477503818296242451618560368057582372347252595214548705383094347985\\
6996102071518084671186166493138564832591058409210861698925277842727414\\
50550717673224011318075568803\\}\)

Ustalić pięć ostatnich cyfr liczb x, y, z.

3.) Niech \(\displaystyle{ a_{0} < a_{1} < a_{2} < \ldots < a_{n}}\) są dodatnimi liczbami całkowitymi. Udowodnić

\(\displaystyle{ \frac{1}{NWW(a_{0},a_{1})}+ \frac{1}{NWW(a_{1},a_{2})}+ \ldots + \frac{1}{NWW(a_{n-1},a_{n})} \le 1- \frac{1}{2^n}}\)

4.) Znaleźć rozwiązanie dla \(\displaystyle{ x^2 +x +34 \equiv 0 \pmod{81}}\)

5.) Jeśli liczba \(\displaystyle{ X3640548981270644Y}\) jest podzielna przez \(\displaystyle{ 99}\), obliczyć parę cyfr \(\displaystyle{ (X,Y).}\)

6.) Obliczyć \(\displaystyle{ x}\) z (\(\displaystyle{ 10^{12}+25)^2 - (10^{12}-25)^2 = 10^x}\)

7.) Liczba \(\displaystyle{ 27 \ 000 \ 001}\) ma dokładnie cztery czynniki pierwsze. Znajdź ich sumę.

[mol_ksiazkowy]

ad 5

Ukryta treść:    

podzielność przez 11
\(\displaystyle{ x+6+0+4+9+1+7+6+4- (3+4+5+8+8+2+0+4+y) = x-y+3}\) jest podzielne przez 11
podzielność przez 9
\(\displaystyle{ 71+ x+y}\) jest podzielne przez 9

stąd
\(\displaystyle{ \begin{cases} x-y = 8\\x+y = 10\end{cases}}\)
tj.
\(\displaystyle{ \begin{cases} x=9\\ y= 1\end{cases}}\)

ad 6

Ukryta treść:    

\(\displaystyle{ (a+b)^2 - (a-b)^2 = 4ab}\) tj. \(\displaystyle{ x=14}\)

-- 10 czerwca 2016, 10:44 --

ad 7

Ukryta treść:    

te dzielniki to \(\displaystyle{ 7, \ 43, \ 271 , \ 331}\)

-- 10 czerwca 2016, 11:18 --ad 4

Ukryta treść:    

Jeśli \(\displaystyle{ x^2+x+34}\) jest podzielne przez 9 to \(\displaystyle{ x=9y+7}\) jednak \(\displaystyle{ x^2+x+34 = 9(9y^2+ 5(3y+2))}\) nie dzieli się przez 9, bo \(\displaystyle{ 3y+2}\) nie dzieli się przez 3

[Premislav]

3.:    

Przypomnijmy, że \(\displaystyle{ \NWW(a,b)\cdot \NWD(a,b)=ab}\) dla całkowitych dodatnich \(\displaystyle{ a,b.}\) Wobec tego:
\(\displaystyle{ \frac{1}{NWW(a_{0},a_{1})}+ \frac{1}{NWW(a_{1},a_{2})}+ \ldots + \frac{1}{NWW(a_{n-1},a_{n})} = \sum_{i=0}^{n-1} \frac{\NWD(a_{i},a_{i+1})}{a_{i}a_{i+1}}}\)
Zauważmy, że skoro \(\displaystyle{ a_{i+1}>a_{i}}\), to
\(\displaystyle{ \frac{\NWD(a_{k},a_{k+1})}{a_{k}a_{k+1}} \le \frac{1}{2a_{k}}}\). Uzasadnienie:
dla liczb całkowitych dodatnich \(\displaystyle{ x>y}\) mamy \(\displaystyle{ \NWD(x,y) \le \frac{x}{2}}\), ponieważ skoro \(\displaystyle{ x> y}\), to dla pewnego \(\displaystyle{ p}\) pierwszego mamy \(\displaystyle{ v_{p}(x)>v_{p}(y)}\) (uzasadnienie: rozpatrzmy wszystkie liczby pierwsze \(\displaystyle{ p_{i}}\), które występują w rozkładzie \(\displaystyle{ x}\) lub \(\displaystyle{ y}\) na czynniki pierwsze; gdyby było dla każdego \(\displaystyle{ i}\) coś takiego: \(\displaystyle{ v_{p_{i}}(y)\ge v_{p_{i}}(x)}\), to \(\displaystyle{ y\ge x}\), sprzeczność), a wtedy \(\displaystyle{ \NWD(x,y) \le \frac{x}{p^{v_{p}(x)-v_{p}(y)}} \le \frac{x}{p} \le \frac{x}{2}}\);
równość zachodzi, gdy \(\displaystyle{ a_{k+1}=2a_{k}}\)

W połączeniu z trywialną indukcją po \(\displaystyle{ n}\) i zastosowaniem wzoru na sumę wyrazów ciągu geometrycznego dostajemy, że tę sumę można z góry ograniczyć przez
\(\displaystyle{ \frac{1}{2a_{0}} \frac{\left( \frac{1}{2a_{0}} \right)^{n}-1 }{ \frac{1}{2a_{0}} -1}}\).
Oczywiście im większe jest \(\displaystyle{ a_{0}}\), tym mniejsze jest ograniczenie górne tej sumy (co dużo łatwiej widać z postaci przed zwinięciem), więc szacując to jeszcze raz z góry, kładziemy \(\displaystyle{ a_{0}=1}\) - najmniejsze, jakie możemy i koniec.

[mol_ksiazkowy]

1 a

Ukryta treść:    

ale \(\displaystyle{ (x^3+1)(y+x^3) = 3^n \cdot 7^{2n}}\) jest możliwe np. gdy \(\displaystyle{ x=2}\) ....?

[Elayne]

Do pierwszego zadania wdał się mały chochlik, poprawiłem.

[Chewbacca97]

mol_ksiazkowy, mógłbyś napisać coś więcej o zadaniu siódmym?

[Elayne]

Zadanie Ad.7.)

Ukryta treść:    

Ad.7.) Zauważmy \(\displaystyle{ 300^3 +1 = 2 700 001}\).
Uprzedzając fakty w tym zadaniu przydadzą się wzory skróconego mnożenia na:
- sumę sześcianów: \(\displaystyle{ a^3 + b^3 = (a+b)(a^2 - ab + b^2)}\)
- kwadrat sumy: \(\displaystyle{ (a+b)^2= a^2 + 2ab + b^2}\)
oraz wzór wyrażający związek między sumą, różnicą i iloczynem dwóch liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\):
\(\displaystyle{ ab = \left(\frac{a+b}{2} \right)^2 - \left(\frac{a-b}{2} \right)^2}\)

\(\displaystyle{ 27000001 = 300^3 + 1^3\\
= (300 + 1)(300^2 - 300 + 1)\\
= 301((300^2 + 2 \cdot 300 \cdot 1 + 1^2) - 900)\\
= 301((300 + 1)^2 - 900)\\
= 301(301^2 - 30^2)\\
= 301 \cdot (271 \cdot 331)\\
= 7 \cdot 43 \cdot 271 \cdot 331.}\)

Na zakończenie zadania dodajmy czynniki pierwsze by uzyskać odpowiedź: \(\displaystyle{ 7 + 43 + 271 + 331= 652}\)

[mol_ksiazkowy]

1

Ukryta treść:    

szkic
Z tego układu wynika że
\(\displaystyle{ (x^3+y+1)^2+ z^9 =147^{157} + 157^{147} + 1 \equiv \ 14 \ (mod \ 19)}\)
który jest sprzeczny /co jest kwestią “technicznego” sprawdzenia/ wartości reszt tego wyrażenia

[Sylwek]

4 (uwagi):    

Najpierw rozwiązałem, potem zauważyłem, że moje rozwiązanie neguje rozwiązanie mola (powyższe rozwiązanie nie jest poprawne - wystarczy \(\displaystyle{ x=3y+1}\)), a potem zauważyłem błąd w swoim rozumowaniu. Poniżej jest już OK.

4:    

Podana kongruencja jest równoważna \(\displaystyle{ 4x^2 + 4x + 4 \cdot 34 \equiv 0 \pmod{81}}\), czyli \(\displaystyle{ (2x+1)^2 + 135 \equiv 0 \pmod{81}}\). To oznacza, że \(\displaystyle{ 27|(2x+1)^2}\), więc \(\displaystyle{ 9|(2x+1)}\). To pociąga za sobą podzielność \(\displaystyle{ 81|(2x+1)^2}\), zatem \(\displaystyle{ (2x+1)^2 + 135 \equiv 135 \not\equiv 0 \pmod{81}}\).

2 (uwagi):    

Jestem ciekawy zadania 2 - sprawdziłem tylko w Wolframie sumę cyfr (1451, i tak musiałem wrzucać tę liczbę "kawałkami"), więc nie jest to podzielne przez 3. Wyczuwam matematyczny trolling we wrzuceniu tego zadania do zestawu, ale mogę się mylić. Elayne?

[Elayne]

Ad 2:    

Jest to bardzo trudne zadanie. Należy podać jaki iloczyn trzech „liczb” kończy się na: \(\displaystyle{ 68 \ 803}\). Zauważmy, że jest to iloczyn liczb pierwszych \(\displaystyle{ 7 \cdot 9829}\).
Załóżmy, że mamy dwie liczby pierwsze, np. \(\displaystyle{ 3823}\) oraz \(\displaystyle{ 4649}\).
\(\displaystyle{ 3823 \cdot 4649 = 17 \ 773 \ 127}\) - jeśli tę liczbę „złamiemy” na środku \(\displaystyle{ [3,4]}\) otrzymamy liczbę pierwszą: \(\displaystyle{ 15 \ 293 \ 947}\).
\(\displaystyle{ 17 \ 773 \ 127 - 15 \ 293 \ 947 = 2 \ 479 \ 180}\)
Jednym z czynników liczby \(\displaystyle{ 2 \ 479 \ 180}\) jest para liczb \(\displaystyle{ 3820 \cdot 649}\).
W tym zadaniu należy ten proces odwrócić, wtedy otrzymamy iloczyn czterech liczb pierwszych który spełnia postawione kryteria, np: \(\displaystyle{ 3 \cdot 4201 \cdot 44579 \cdot 9619}\).

[Sylwek]

2 - pytania:    

Ja się pogubiłem...

Czy to jest 5 różnych zadań w ramach zadania nr 2? :-D

Czy chodzi o 3, czy o 4 liczby pierwsze, których iloczyn/iloczyny podałeś?

[Elayne]

Ad 2.:    

Jest to szkic rozwiązania. Podałem jako przykład: \(\displaystyle{ 3 \cdot 4201 \cdot 44579 \cdot 9619}\)
więc są to iloczyny trzech liczb które kończą się takimi cyframi:
\(\displaystyle{ 12603, 44579, 09619}\);
\(\displaystyle{ 04201, 44579, 28857}\);

-- 6 kwi 2017, o 20:07 --

Ad 4:    

Zadanie można też rozwiązać przy pomocy lematu Hensela.

[Elayne]

Ad 1.:    

Kod: Zaznacz cały

https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_2

Z funkcji Carmichaela.

\(\displaystyle{ x^{6} + x^{3} + x^{3}y + y = 147^{157},\\
x^{3} + x^{3}y + y^{2} + y + z^{9} = 157^{147} \\

(x^3 + y + 1)^2 + z^9 = 147^{157} + 157^{147} + 1 \\
\\
9 = \frac{1}{2} 18 = \frac{1}{2} \lambda (19) = \frac{1}{2} \lambda (27) = \frac{1}{2} \lambda (54) \\ \\
z^9 \ \equiv \ 0, \ \pm 1 \ \ (mod \ 19) \\
147^{157} \ \equiv \ (-5)^{18 \cdot 8 + 13} \ \equiv \ -5^{13} \ \equiv \ 2 \ (mod \ 19) \\
157^{147} \ \equiv \ (5)^{18 \cdot 8 + 3} \ \equiv \ 5^3 \ \equiv \ 11 \ (mod \ 19) \\
\\
(x^3 + y + 1)^2 = 147^{157} + 157^{147} + 1 - z^9 \ \equiv \ 13, \ 14, \ 15 \ (mod \ 19) \\
\\
\left[ \frac{13}{19} \right] = -1; \ \left[ \frac{14}{19}\right] = -1; \ \left[ \frac{15}{19}\right] = -1}\)