[MIX] Różniaste z podzielności

[Qń]

11:    

Tak. Z Małego Twierdzenia Fermata wynika, że:
\(\displaystyle{ a^p \equiv a\pmod{p}\\
a^q \equiv a\pmod{q}}\)
Stąd i z założenia (i z tego, że \(\displaystyle{ p,q}\) są względnie pierwsze) wynika, że:
\(\displaystyle{ a^p \equiv a\pmod{pq}\\
a^q \equiv a\pmod{pq}}\)
a zatem:
\(\displaystyle{ a^{pq}=(a^p)^q}\equiv a^q \equiv a \pmod {pq}}\).

Q.

[Premislav]

24.:    

Ta liczba zwija się do \(\displaystyle{ 10 ^{202}+10 ^{101}+1}\), a to dziwnie przypomina czynnik \(\displaystyle{ a ^{2}+ab+b ^{2}}\) ze wzoru skróconego mnożenia na różnicę sześcianów, dla \(\displaystyle{ a=10 ^{101}}\), \(\displaystyle{ b=1}\)(albo na odwrót). Oznaczając tę długą liczbę z zadania przez \(\displaystyle{ m}\), zapisujemy \(\displaystyle{ m=10 ^{202}+10 ^{101}+1}\) i mnożymy stronami tę równość przez \(\displaystyle{ 10 ^{101}-1}\), otrzymując \(\displaystyle{ (10 ^{101}-1)m=101 ^{303}-1}\). Zauważmy, że \(\displaystyle{ 10 ^{3}=1110-111+1\equiv 1\pmod{37}}\), a więc \(\displaystyle{ 10 ^{101}\equiv100\equiv 26\pmod{37}}\), a także \(\displaystyle{ 10 ^{303}\equiv 1\pmod{37}}\). Zatem \(\displaystyle{ 37}\) dzieli iloczyn \(\displaystyle{ (10 ^{101}-1)m}\), a nie dzieli \(\displaystyle{ 10 ^{101}-1}\), więc jako że \(\displaystyle{ 37}\) jest liczbą pierwszą, to \(\displaystyle{ 37}\) musi dzielić \(\displaystyle{ m}\), co było do udowodnienia.

[Qń]

25:    

Oznaczmy \(\displaystyle{ NWD(a,b)=d}\), wtedy oczywiście \(\displaystyle{ NWW(a,b) = \frac{ab}{d}}\).
Niech ponadto \(\displaystyle{ a=dx,b=dy}\) (oczywiście \(\displaystyle{ x\ge y}\)).

Równość z zadania przekształca się wtedy do:
\(\displaystyle{ d + dxy + dx + dy = d^2xy}\)
czyli:
\(\displaystyle{ xy+x+y+1= dxy\\
(x+1)(y+1)=dxy}\)

Skoro \(\displaystyle{ x}\) dzieli prawą stronę, to i lewą - i widać, że musi być \(\displaystyle{ x|(y+1)}\) oraz analogicznie \(\displaystyle{ y|(x+1)}\). W szczególności stąd wynika, że \(\displaystyle{ x\le y+1\le x+2}\), skąd dostajemy (pamiętając, że \(\displaystyle{ x\ge y}\)), że \(\displaystyle{ x=y+1}\) lub \(\displaystyle{ x=y}\). W pierwszym wypadku oznacza to, że \(\displaystyle{ y|(y+2)}\) czyli \(\displaystyle{ y|2}\), czyli \(\displaystyle{ y\in\{1,2\}}\), a w drugim z \(\displaystyle{ y|(y+1)}\) widać, że \(\displaystyle{ y=1}\). Tak więc \(\displaystyle{ (x,y) \in \{(3,2),(2,1),(1,1)\}}\).

Jeśli \(\displaystyle{ x=3,y=2}\) to łatwo policzyć, że \(\displaystyle{ d=2}\) i otrzymujemy rozwiązanie \(\displaystyle{ a=6,b=4}\).
Jeśli \(\displaystyle{ x=2,y=1}\) to łatwo policzyć, że \(\displaystyle{ d=3}\) i otrzymujemy rozwiązanie \(\displaystyle{ a=6,b=3}\).
Jeśli \(\displaystyle{ x=1,y=1}\) to łatwo policzyć, że \(\displaystyle{ d=4}\) i otrzymujemy rozwiązanie \(\displaystyle{ a=4,b=4}\).

Q.

[Premislav]

7.:    

Część pierwszą wykażę, pokazując, że dla \(\displaystyle{ n \in \NN}\) jest\(\displaystyle{ 10 | F _{15n}}\) (bo \(\displaystyle{ 1005=900+90+15=67 \cdot 15}\)). Lemat: dla \(\displaystyle{ k}\) naturalnych dodatnich, \(\displaystyle{ n}\) naturalnych jest \(\displaystyle{ F _{n+k}=F _{k}F _{n+1}+F _{k-1}Fn}\). Dowód lematu: indukcja po \(\displaystyle{ k}\), dla \(\displaystyle{ k=1}\) teza lematu zachodzi, zakładając zaś tezę dla \(\displaystyle{ k \le m}\) otrzymujemy \(\displaystyle{ F _{n+m+1}=F _{n+m}+F _{n+m-1}=F _{m} F _{n+1}+F _{m-1}F _{n}+F _{m-1}F _{n+1}+F _{m-2}F _{n}=F _{m+1}F _{n+1}+F _{m}F _{n}}\). skorzystałem z założenia indukcyjnego dla \(\displaystyle{ m}\), \(\displaystyle{ m-1}\) oraz rekurencyjnej definicji ciągu Fibonacciego. Teraz przejdźmy do dowodu pierwszej części (ponownie indukcja, tym razem po \(\displaystyle{ n}\)):
\(\displaystyle{ F _{15}=610}\), więc \(\displaystyle{ 10 | F _{15}}\); zakładając dla pewnego\(\displaystyle{ n \in \NN}\), że \(\displaystyle{ 10 |F _{15n}}\) dostajemy \(\displaystyle{ F _{15n+15}=(lemat)=F _{15}F _{15n+1}+F _{14}F _{15n}}\) (a z bazy indukcyjnej jest \(\displaystyle{ 10 | F _{15}}\), zaś z założenia indukcyjnego \(\displaystyle{ 10 | F _{15n}}\)), co kończy dowód własności; zatem \(\displaystyle{ F _{1005}}\) jest podzielne przez \(\displaystyle{ 10}\), co było do wykazania.
Druga część: nie wymyśliłem niestety nic lepszego niż overkill twierdzeniem mówiącym iż \(\displaystyle{ NWD(F _{m},F _{n})=F _{NWD(m,n)}}\). Ponieważ \(\displaystyle{ 50 | F _{75k}}\), a w szczególności \(\displaystyle{ 50|F _{75}}\), zaś \(\displaystyle{ NWD(1005,75)=15}\) (przypominam, że \(\displaystyle{ F _{15}=610}\)) , to z powyżej przywołanego twierdzenia \(\displaystyle{ 50}\) nie dzieli \(\displaystyle{ F _{1005}}\), bo gdyby dzieliło, to dzieliłoby też\(\displaystyle{ NWD(F _{75},F _{1005})}\), ale tak nie jest.

[gryxon]

33:    

Rozpatrzmy liczby:
\(\displaystyle{ p-2 = 15g+5 = 5(3g+1)}\)
\(\displaystyle{ p=15g+7}\)
\(\displaystyle{ p+2 = 15g+9 = 3(5g+3)}\)

Oczywiście \(\displaystyle{ p-2}\) oraz \(\displaystyle{ p+2}\) są złożone dla \(\displaystyle{ g>1}\)
Rozpatrzmy ciąg arytmetyczny: \(\displaystyle{ a_{0}=7, r=15}\)
Wtedy: \(\displaystyle{ a_{n}=15n+7}\)
Zgodnie z twierdzeniem Dirichleta w tym ciągu jest nieskończenie wiele liczb pierwszych.
Tak więc liczb pierwszych w postaci \(\displaystyle{ 15g+7}\) jest nieskończenie wiele.

[Qń]

1:    

Mamy \(\displaystyle{ 2304=2^8\cdot 3^2= 256 \cdot 9}\).
Oczywiście \(\displaystyle{ 7^3\equiv 1\pmod 9}\) skąd \(\displaystyle{ 7^{63}\equiv 1\pmod 9}\) i \(\displaystyle{ 7^{64}\equiv 7\pmod 9}\). Mamy też:
\(\displaystyle{ 7^{64}-1= (7^{32}+1)(7^{16}+1)(7^8+1)(7^4+1)(7^2+1)(7+1)(7-1)}\)
i każdy z nawiasów jest podzielny przez \(\displaystyle{ 2}\), a jeden nawet przez \(\displaystyle{ 8}\), stąd całość na pewno jest podzielna przez \(\displaystyle{ 2^8}\), czyli \(\displaystyle{ 7^{64}\equiv 1\pmod{256}}\).

Tak więc dla \(\displaystyle{ n=7^{64}}\) jest:
\(\displaystyle{ \begin{cases}
n\equiv 7\pmod 9\\
n\equiv 1\pmod{256}
\end{cases}}\)
co łatwo rozwiązać stosując dowolny algorytm dla układów kongruencji spełniających założenia Chińskiego Twierdzenia o Resztach - wyjdzie \(\displaystyle{ n\equiv 1537 \pmod{2304}}\).

Q.

[gryxon]

27:    

Jeżeli \(\displaystyle{ 7|n^{3}+3^{n}}\) to:
\(\displaystyle{ n \not=7k \Rightarrow n^{3} = \pm 1 \ (mod \ 7) \Rightarrow 3^{n} = \mp 1 \ (mod \ 7)}\)
Wtedy: \(\displaystyle{ 3^{n}n^{3} + 1 = 0 \ (mod \ 7)}\)

Analogicznie udowadniamy implikację w drugą stronę. Kluczem w tym zadaniu jest fakt, że:
\(\displaystyle{ n^{3} = \pm 1 \ (mod \ 7)}\)

[Premislav]

22.:    

Ja jako trzecią sprawdziłem \(\displaystyle{ 331}\), ale to chyba przypadek, czekam na ładniejsze rozwiązanie, z wytłumaczeniem, czemu akurat ta. Moje: \(\displaystyle{ 999951=3 \cdot 333 \cdot 10 ^{3}+3 \cdot 317=3(317+333 \cdot 10^{3})}\), ale \(\displaystyle{ 317\equiv -14\pmod{331}\wedge 333\equiv2\pmod{331}\wedge10^{3}\equiv 7\pod{331}}\), więc \(\displaystyle{ 999951\equiv 0\pmod {331}}\)

[mol_ksiazkowy]

ad 29

Ukryta treść:    

chochlik nieduży : s=66

ad 1

Ukryta treść:    

zadanie na bazie tego ze \(\displaystyle{ 49^{n}-2352n - 1}\) dzieli sie przez 2304

ad 14

Ukryta treść:    

dla a=4 zadanie Sophie Germain ...

[Qń]

3:    

Dla \(\displaystyle{ p=5}\) takie \(\displaystyle{ n}\) nie istnieje, bo \(\displaystyle{ 9i_m}\) nigdy nie jest podzielne przez \(\displaystyle{ 5}\). Natomiast dla \(\displaystyle{ p>5}\) żądane \(\displaystyle{ n}\) istnieje zawsze, bo dla pewnego \(\displaystyle{ m}\) mamy \(\displaystyle{ p|9i_m}\).

Rozważmy bowiem \(\displaystyle{ p+1}\) liczb \(\displaystyle{ 9i_1,9i_2, \ldots , 9i_{p+1}}\). Z Zasady Szufladkowej Dirichleta pewne dwie \(\displaystyle{ 9i_k,9i_l}\) (\(\displaystyle{ k>l}\)) dają tę samą resztę z dzielenia przez \(\displaystyle{ p}\). W takim razie przez \(\displaystyle{ p}\) podzielna jest liczba: \(\displaystyle{ 9(i_k-i_l)= 9i_{k-l}\cdot 10^{l}}\). Ale skoro \(\displaystyle{ p>5}\), to \(\displaystyle{ NWD(p,9\cdot 10^l)=1}\), a stąd \(\displaystyle{ p|9i_{k-l}}\) czyli koniec.

Q.

[yorgin]

Z nudów (beznadziejna pogoda, niskie ciśnienie itp)

12:    

Można zapewne przypałować chińskie o resztach, ale ja go nie pamiętam, więc robię po swojemu.

Z pierwszego równania wynika, że

\(\displaystyle{ n=13k+2}\)

Po podstawieniu do drugiego mamy

\(\displaystyle{ 13k+2\equiv 3\mod 11\\
2k\equiv 1\mod 11\\
k=11\ell+6}\)

I podobnie, po podstawieniu do trzeciego wyjdzie

\(\displaystyle{ \ell\equiv 1\mod 7\\
\ell=7m+3}\)

Zbieramy wszystko:

\(\displaystyle{ n=13(11(7m+3)+6)+2=1001m+509, m\in\ZZ}\)

stąd najmnieszą dodatnią liczbą jest \(\displaystyle{ 509}\).

Metoda własna, wymyślona lata temu na ćwiczeniach z algebry.

Edit: niskie cisnienie = większa szansa na błedy w dodawaniu. Poprawa tychże.

[kicaj]

16:    

Ponieważ \(\displaystyle{ k\equiv -101 +k (\mbox{mod} 101 )}\) więc
\(\displaystyle{ (50!)^2 +1\equiv 50! (-51 )\cdot...\cdot (-100) +1 \equiv (-1)^{50} 100! +1 \equiv 100! +1 \equiv 0 (\mbox{mod} 101 )}\)
bo \(\displaystyle{ 101}\) jest liczbą pierwszą.

[Qń]

17:    

Trochę topornie:

Oznaczmy \(\displaystyle{ p=274177}\). Wtedy:
\(\displaystyle{ p-1=2^8\cdot 1071}\)
a zatem
\(\displaystyle{ 2^8\cdot 1071\equiv -1\pmod p}\)
co po podniesieniu stronami do potęgi ósmej daje:
\(\displaystyle{ 2^{64}\cdot 1071^8\equiv 1\pmod p}\)
skąd widać, że jeśli \(\displaystyle{ 1071^8\equiv -1\pmod p}\), to otrzymamy tezę. A to już można sprawdzić z kalkulatorem:
\(\displaystyle{ 1071^2= 1147041\equiv 50333\pmod p\\
1071^4\equiv 50333^2=2533510889 \equiv 15409 \pmod p\\
1071^8\equiv 15409^2 = 237437281 \equiv -1 \pmod p}\)

Q.

[Ponewor]

10.:    

Niech \(\displaystyle{ n\mid 3^{n}+1 \wedge n>1 \wedge 2 \nmid n}\)
Skoro \(\displaystyle{ n>1}\), to rozważmy \(\displaystyle{ p}\) - najmniejszy dzielnik pierwszy \(\displaystyle{ n}\). Oczywiście \(\displaystyle{ p \neq 2}\).
Niech \(\displaystyle{ t=\text{ord}_{p}3}\)
Wówczas \(\displaystyle{ 3^{t} \equiv 1 \pmod{p}}\)
Z MTF \(\displaystyle{ t\mid p-1}\)
\(\displaystyle{ p\mid n\mid 3^{n}+1 \\ 3^{n} \equiv -1 \pmod{p} \\ 3^{2n} \equiv 1 \pmod{p}}\)
Zatem
\(\displaystyle{ t \nmid n \wedge t\mid 2n \Rightarrow 2\mid t \Rightarrow t=2k \Rightarrow 2k\mid 2n \Rightarrow k\mid n}\)
Zauważmy, że musi być \(\displaystyle{ k>1}\), bo w przeciwnym razie:
\(\displaystyle{ k=1 \Rightarrow t=2 \Rightarrow 3^{2} \equiv 1 \pmod{p} \Rightarrow p=2}\)
Skoro więc \(\displaystyle{ k>1}\), to rozważmy \(\displaystyle{ p_{1}}\) - dowolny dzielnik pierwszy \(\displaystyle{ k}\).
Mamy \(\displaystyle{ p_{1} \mid k \mid n}\)
i jednocześnie \(\displaystyle{ p_{1}\midk\mid t \mid p-1 \Rightarrow p_{1}\le k\le t \le p-1 < p}\)
wbrew określeniu liczby \(\displaystyle{ p}\).

[Premislav]

4.:    

Przekształcę trochę liczbę \(\displaystyle{ \frac{10 ^{20000} }{10 ^{100}+3 }}\). Otóż dzieląc licznik i mianownik przez \(\displaystyle{ 10 ^{100}}\) otrzymuję \(\displaystyle{ \frac{10 ^{200} }{1+ \frac{3}{10 ^{100} } }}\), co oczywiście jest równe \(\displaystyle{ \frac{10 ^{200} }{1-(- \frac{3}{10 ^{100} } ) }}\). W tej postaci łatwiej zobaczyć, że liczba, której podłogę mam badać, to suma szeregu geometrycznego o pierwszym wyrazie równym \(\displaystyle{ 10 ^{200}}\) i ilorazie wynoszącym \(\displaystyle{ -\frac{3}{10 ^{100} }}\), czyli \(\displaystyle{ 10 ^{200}-3 \cdot 10^{100}+9-27\cdot 10^{-100}+...}\), przy czym ten ogon poczynając od czwartego miejsca sumuje się do \(\displaystyle{ \frac{-27}{10 ^{100}-3 }}\), co jest ujemne i większe od \(\displaystyle{ -1}\). Zatem łatwo widać, że podłoga z liczby podanej w zadaniu daje resztę \(\displaystyle{ 8}\) przy dzieleniu przez \(\displaystyle{ 10}\).