[MIX] Różniaste z podzielności

[mol_ksiazkowy]

1. rozwiązane przez Qnia
Wyznaczyć takie \(\displaystyle{ n}\) że \(\displaystyle{ 7^{64} \equiv \ n \ (mod \ 2304)}\).
2. Wykazać, że \(\displaystyle{ i_{1977}}\) ma co najwyżej 364 dzielniki naturalne; przy czym \(\displaystyle{ i_n= \underbrace{1 \cdots 1}_{n}}\)
3. rozwiązane przez Qnia
Jakie liczby pierwsze \(\displaystyle{ p>3}\) mają wielokrotność \(\displaystyle{ np}\) będącą
liczbą dziewiątkową (tj. \(\displaystyle{ 9i_n}\)); mamy np. \(\displaystyle{ 13 \cdot 76923 = 999 999}\) ?
4. rozwiązane przez Premislava
Jaka jest reszta z dzielenia \(\displaystyle{ \lfloor \frac{10^{20 000}}{10^{100}+3 } \rfloor}\) przez \(\displaystyle{ 10}\) ?
5. rozwiązane przez Premislava i Qnia
Dowieść, że liczba \(\displaystyle{ 7^{37}+ 13^{37}+ 19^{37}}\) jest podzielna przez 39.
6. rozwiązane przez Qnia
Udowodnić, że liczba \(\displaystyle{ 5^{6614} - 12^{857} -1}\) jest podzielna przez 7
7. rozwiązane przez Premislava
Wykazać, że \(\displaystyle{ F_{1005}}\) jest podzielne przez 10 ale nie przez 100
gdzie \(\displaystyle{ F_n}\) to ciąg Fibonacciego
8. rozwiązane przez yorgina
Uzasadnić, że 35-ta liczba Mersenne’a \(\displaystyle{ 2^{35}-1}\) jest podzielna przez 31 i 127.
9. Niech \(\displaystyle{ n= 2^{31}3^{19}}\). Ile jest dzielników liczby \(\displaystyle{ n^2}\) które są mniejsze od \(\displaystyle{ n}\) ale nie dzielą \(\displaystyle{ n}\) ?
1004 ntp
10. rozwiązane przez Ponewora
Dowieść że liczba \(\displaystyle{ 3^n+1}\) nie dzieli się przez \(\displaystyle{ n}\), o ile \(\displaystyle{ n>1}\) jest nieparzyste
11. rozwiązane przez Qnia
Niech \(\displaystyle{ p}\) i \(\displaystyle{ q}\) będą różnymi liczbami pierwszymi. Czy z tego, że \(\displaystyle{ a^p \equiv a \ (mod \ q)}\) i \(\displaystyle{ a^q \equiv a \ (mod \ p)}\) wynika, że \(\displaystyle{ a^{pq} \equiv a \ (mod \ pq)}\) ? Uzasadnić
12. rozwiązane przez yorgina
Wyznaczyć najmniejszą liczbę naturalną \(\displaystyle{ n>1}\) że
\(\displaystyle{ \begin{cases} n \equiv 2 \ (mod \ 13)\\ n \equiv 3 \ (mod \ 11)\\ n \equiv 5 \ (mod \ 7)\end{cases}}\)
13. rozwiązane przez Qnia
Wykazać że gdy \(\displaystyle{ n}\) jest liczbą naturalną, to \(\displaystyle{ 5^{2n+1}2^{n+2}+ 3^{n+2} 2^{2n+1}}\) jest podzielne przez 19
14. rozwiązane przez yorgina
Udowodnić, że istnieje nieskończenie wiele liczb \(\displaystyle{ a}\), że \(\displaystyle{ n^4+a}\) jest złożona dla każdej liczby naturalnej \(\displaystyle{ n}\); podać przykład trzech takich liczb \(\displaystyle{ a}\).
15. rozwiązane przez Ponewora
Czy istnieje liczba o sumie cyfr mniejszej niż \(\displaystyle{ n}\), podzielna przez \(\displaystyle{ i_n}\) ?
16. rozwiązane przez kicaja
Wykazać że liczba \(\displaystyle{ 50! ^2 +1}\) jest złożona
17. rozwiązane przez Qnia
Wykazać, że 6-ta liczba Fermata \(\displaystyle{ F_6= 2^{2^6}+1}\) jest podzielna przez \(\displaystyle{ 274 177}\)
18 rozwiązane przez Qnia
Udowodnić że liczba \(\displaystyle{ 53^{103}+ 103^{53}}\) jest podzielna przez 78
19. Wyznaczyć trzy dzielniki pierwsze 71-ej liczby Mersenne’a \(\displaystyle{ 2^{71}-1}\)
20. rozwiązane przez Qnia
Wykazać, że liczba \(\displaystyle{ 3^{1974}+ 5^{1974}}\) dzieli się przez 13

21. rozwiązane przez Qnia
Czy któraś z liczb \(\displaystyle{ 2^{100} - 1}\) i \(\displaystyle{ 2^{100} + 1}\) jest podzielna przez 7 ?
22. rozwiązane przez Premislava
Liczba \(\displaystyle{ n= 999 \ 951}\) jest podzielna przez liczbą pierwszą \(\displaystyle{ p}\) taką, że \(\displaystyle{ 300< p<400}\). Wyznaczyć \(\displaystyle{ p}\).
23. rozwiązane przez Qnia
Czy istnieje liczba całkowita \(\displaystyle{ n}\) taka, że \(\displaystyle{ n^2 - 2}\) jest podzielna przez 231 ?
24. rozwiązane przez Premislava
Udowodnić, że liczba \(\displaystyle{ 1 \underbrace{0 \ldots 0}_{100}1 \underbrace{0 \ldots 0}_{100} 1}\) jest podzielna przez 37.
25. rozwiązane przez Qnia
Wyznaczyć wszystkie takie \(\displaystyle{ a, b}\) że:
\(\displaystyle{ \begin{cases} a \geq b\\NWD(a,b)+ NWW(a,b)+a+b=ab\end{cases}}\)
jp 96
26. rozwiązane przez Premislava
Wyznaczyć \(\displaystyle{ n}\); o ile to możliwe; jak najmniejsze takie, że \(\displaystyle{ 2^n \equiv 1 \ (mod \ 125)}\)
27. rozwiązane przez gryxona
Dowieść że gdy liczba \(\displaystyle{ 3^n+ n^3}\) jest podzielna przez 7 to liczba \(\displaystyle{ 3^n n^3 + 1}\) też jest podzielna przez 7 (i na odwrót)
28. rozwiązane przez yorgina
Dla jakich liczb naturalnych \(\displaystyle{ n}\) liczba \(\displaystyle{ 3^n -1}\) jest podzielna przez 7 ?
29. rozwiązane przez yorgina
Niech \(\displaystyle{ s}\), \(\displaystyle{ t}\) będą wykładnikami liczb 7 i 3 w rozwinięciu na czynniki pierwsze odpowiednio liczb \(\displaystyle{ 400!}\) oraz \(\displaystyle{ ( (3!)! )!}\). Obliczyć \(\displaystyle{ s+t}\)
30. Obliczyć \(\displaystyle{ NWD(5^n+7^n, 5^m+7^m)}\), gdzie \(\displaystyle{ m}\) i \(\displaystyle{ n}\) są względnie pierwsze
jp, 96
31. rozwiązane przez Premislava
Czy jeśli \(\displaystyle{ n}\) jest kwadratem i sześcianem liczby naturalnej to \(\displaystyle{ n=7k}\) albo \(\displaystyle{ n=7k+1}\) dla jakiejś liczby całkowitej \(\displaystyle{ k}\) ?
32. rozwiązane przez Qnia
Rozwiązać kongruencję
\(\displaystyle{ x^2 \equiv -1 \ (mod \ 37)}\)
33. rozwiązane przez gryxona
Dowieść istnienia nieskończenie wielu liczb pierwszych \(\displaystyle{ p}\), że \(\displaystyle{ p-2}\) oraz \(\displaystyle{ p+2}\) są złożone
>
34. rozwiązane przez Premislava
extra Wykazać, że gdy \(\displaystyle{ n}\) jest liczbą naturalną to \(\displaystyle{ 1492^n - 1770^n -1863^n + 2141^n}\) dzieli się przez 1946.
tematy: tw, Lejeune Dirichleta, CRT, mtF, kongruencje,

[Qń]

20:    

Mamy:
\(\displaystyle{ 3^3\equiv 1 \pmod{13} \Rightarrow (3^3)^{658}=3^{1974} \equiv 1 \pmod{13}\\
5^2\equiv -1\pmod{13} \Rightarrow (5^2)^{987}=5^{1974}\equiv -1\pmod{13}}\)
i dodanie stronami dwóch ostatnich kongruencji daje nam tezę.

Q.

[yorgin]

8:    

Pierwsza kongruencja:

\(\displaystyle{ 32=2^5\equiv 1\mod 31}\), stąd \(\displaystyle{ 2^{35}=(2^5)^7\equiv 1\mod 31}\).

Podobnie druga:

\(\displaystyle{ 128=2^7\equiv 1\mod 127}\), stąd \(\displaystyle{ 2^{35}=(2^7)^5\equiv 1\mod 127}\).

[Qń]

21:    

Nie, mamy bowiem:
\(\displaystyle{ 2^{100} = 2\cdot (2^3)^{33} = 2\cdot 8^{33} \equiv 2\pmod{7}}\)
skąd
\(\displaystyle{ 2^{100}+1\equiv 3\pmod{7}\\
2^{100}-1\equiv 1\pmod{7}}\)

Q.

[yorgin]

29:    

Nie wiem, czy są na to jakieś wzory, pewnie coś się do tego znajdzie.

Liczba siódemek w rozwinięciu\(\displaystyle{ 400!}\) to

\(\displaystyle{ \left[ \frac{400}{7}\right] +\left[ \frac{400}{49}\right] +\left[ \frac{400}{343}\right]}\).

Liczę najpierw, ile jest wielokrotności \(\displaystyle{ 7}\), potem \(\displaystyle{ 49}\) i \(\displaystyle{ 343}\). Te wielokrotności mają zawsze wkład równy \(\displaystyle{ 1}\), gdyż \(\displaystyle{ 7^2}\) zostało już wliczone na poczet wielokrotności siódemek, podobnie \(\displaystyle{ 7^3}\) w wieloktorności \(\displaystyle{ 7}\) oraz \(\displaystyle{ 49}\).

Sumarycznie mamy

\(\displaystyle{ s=57+8+1=66}\)

Analogiczine, ponieważ \(\displaystyle{ ((3!)!)!=720!}\), więc

\(\displaystyle{ t=\sum\limits_{k=1}^5\left[ \frac{720}{3^k}\right]=240+80+25+8+2=355}\)

\(\displaystyle{ s+t=355+66=421}\).

Mam nadzieję, że tym razem dodawanie i dzielenie jest poprawanie

Edit: Małe błędy. Miałem rację, dodawanie najtudniejsze

[Qń]

13:    

\(\displaystyle{ 5^{2n+1}2^{n+2}+ 3^{n+2} 2^{2n+1}= 20\cdot 50^n +18\cdot 12^n \equiv \\ \equiv 20\cdot 12^n+18\cdot 12^n =38 \cdot 12^n \equiv 0 \pmod{19}}\)

Q.

[yorgin]

Na zmianę

14:    

Wystarczy wziąć \(\displaystyle{ a=4k^4, k=2,3,4,\ldots}\)

Mamy bowiem

\(\displaystyle{ n^4+a=n^4+4k^4=(n^4+4k^2n^2+4k^4)-4k^2n^2=(n^2+2k^2)^2-(2kn)^2=}\)
\(\displaystyle{ =(n^2+2k^2-2kn)(n^2+2k^2+2kn)}\)

Wystarczy teraz zauważyć, że

\(\displaystyle{ n^2+2k^2-2kn=(n-k)^2+k^2\geq k^2}\),

więc począwszy od \(\displaystyle{ k=2}\) zawsze dostaniemy co najmniej dwa różne dzielniki liczby \(\displaystyle{ n^4+a}\).

Przykłady są dla \(\displaystyle{ k=2,3,4}\), odpowiednio dostajemy \(\displaystyle{ 64, 324, 1024}\)

[Qń]

23:    

Gdyby liczba \(\displaystyle{ n^2-2}\) była podzielna przez \(\displaystyle{ 231}\), to byłaby podzielna także przez \(\displaystyle{ 3}\). Ale kwadrat liczby naturalnej może dawać tylko reszty \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 3}\), więc \(\displaystyle{ n^2-2}\) może dawać tylko reszty \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) z dzielenia przez \(\displaystyle{ 3}\).

Q.

[yorgin]

28:    

Szukamy takich \(\displaystyle{ n}\), by \(\displaystyle{ 3^n \equiv 1\mod 7}\). Ale kolejne reszty modulo to

\(\displaystyle{ 3^1\equiv 3\mod 7}\)
\(\displaystyle{ 3^2\equiv 2\mod 7}\)
\(\displaystyle{ 3^3\equiv 6\mod 7}\)
\(\displaystyle{ 3^4\equiv 4\mod 7}\)
\(\displaystyle{ 3^5\equiv 5\mod 7}\)
\(\displaystyle{ 3^6\equiv 1\mod 7}\)
\(\displaystyle{ 3^7\equiv 3\mod 7}\)

I cykl się powtarza. Widać więc, że tylko dla \(\displaystyle{ n=6k}\) dostajemy odpowiednią relację. Gdy już to wiemy, możemy się nawet pokusić o coś takiego:

\(\displaystyle{ 3^{6k}-1=(3^6)^k-1=(3^6-1)(1+3+\ldots+(3^6)^{k-1})=728\cdot x=104\cdot 7\cdot x=7u}\).

Zamykam sztafetę w swoim wykonaniu.

[Qń]

6:    

\(\displaystyle{ 5^{6614} - 12^{857} -1\equiv (-2)^{6614} - (-2)^{857} -1=2^{6614} +2^{857} -1=\\ =
2^2\cdot 8^{2206} + 2^2 \cdot 8^{285} \equiv 2^2+2^2-1=7\equiv 0\pmod{7}}\)

Q.

[Premislav]

26.:    

Z twierdzenia Eulera zachodzi \(\displaystyle{ 2 ^{100}\equiv 1\pmod{125}}\), bo \(\displaystyle{ \phi(125)=100}\). Sprawdzamy dzielniki naturalne \(\displaystyle{ 100}\) i najwyraźniej żaden z nich nie spełnia zależności z zadania. Teraz załóżmy nie wprost, że dla co najmniej jednego \(\displaystyle{ k\in \left\{ 0,1,...99\right\}}\) niebędącego dzielnikiem \(\displaystyle{ 100}\) jest \(\displaystyle{ 2 ^{k}\equiv 1\pmod{125}}\), to weźmy najmniejsze \(\displaystyle{ k}\) o tej własności, zapisujemy \(\displaystyle{ 100}\) jako \(\displaystyle{ mk+r}\), gdzie \(\displaystyle{ m \in \NN, r \in \left\{ 1,2,...k-1\right\}}\). To prowadzi do sprzeczności modulo \(\displaystyle{ 125}\) (bo \(\displaystyle{ r<k}\)), czyli dowiodłem, że takiego \(\displaystyle{ k}\) nie ma. Odpowiedź: 100

[Qń]

18:    

Z uwagi na \(\displaystyle{ 78=2\cdot 3\cdot 13}\) wystarczy dowieść podzielności naszej liczby przez \(\displaystyle{ 2,3,13}\). Podzielność przez \(\displaystyle{ 2}\) jest oczywista. Mamy dalej:
\(\displaystyle{ 53^{103}+ 103^{53}\equiv (-1)^{53}+1^{53} =0\pmod{3}}\)
oraz
\(\displaystyle{ 53^{103}+ 103^{53}\equiv 1^{53}+(-1)^{53} =0\pmod{13}}\)
co kończy dowód.

Q.

[Premislav]

5.:    

\(\displaystyle{ 13 ^{37}=13 ^{37}-13+13=13(13 ^{36}-1)+13}\), ale z MTF \(\displaystyle{ 13 ^{2}\equiv 1\pmod{3}}\), więc \(\displaystyle{ 13 ^{36}\equiv 1\pmod{3}}\), wobec czego \(\displaystyle{ 13 ^{37}\equiv 13\pmod{39}}\). Ponadto \(\displaystyle{ (7,39)=1}\) oraz \(\displaystyle{ (19,39)=1}\), więc z tw. Eulera \(\displaystyle{ 7 ^{24}\equiv 1\pmod{39} \wedge 19 ^{24}\equiv 1\pmod{39}}\). Jest też \(\displaystyle{ 19 ^{3}\equiv -5 \pmod{39}}\) oraz \(\displaystyle{ 7 ^{2}\equiv 10\pmod{39}}\), więc \(\displaystyle{ 7 ^{37}\equiv7 ^{13}\equiv 7 \cdot 10 ^{6}\equiv 7\pmod{39}}\) a także \(\displaystyle{ 19 ^{37}\equiv 19 ^{13}\equiv 19\pmod{39}}\). Zatem sumując, mamy \(\displaystyle{ 7 ^{37}+13 ^{37}+19 ^{37} \equiv7+13+19\equiv 0\pmod{37}}\), co było do udowodnienia. Coś mi mówi, że istnieje dużo ładniejsze rozwiązanie, ale jestem zbyt mało inteligentny, by je wymyślić.

[Qń]

32:    

Kongruencja jest równoważna:
\(\displaystyle{ x^2\equiv 36\pmod{37}}\)
skąd \(\displaystyle{ 37|(x-6)(x+6)}\), a więc \(\displaystyle{ x\equiv \pm 6 \pmod{37}}\)

I prostsze rozwiązanie piątego:

5 inaczej:    

Z uwagi na \(\displaystyle{ 39=3\cdot 13}\) wystarczy pokazać podzielność przez \(\displaystyle{ 3}\) i przez \(\displaystyle{ 13}\). Mamy:
\(\displaystyle{ 7^{37}+ 13^{37}+ 19^{37}\equiv 1^{37}+ 1^{37}+ 1^{37}\equiv 0 \pmod 3\\
7^{37}+ 13^{37}+ 19^{37} \equiv 7^{37}+ 0^{37}+ (-7)^{37}=0\pmod{13}}\)
co kończy dowód.

Q.

[Premislav]

31.:    

Liczba naturalna \(\displaystyle{ n}\) jest sześcianem liczby naturalnej wtedy i tylko wtedy, gdy w rozkładzie na czynniki pierwsze każdy wykładnik jest podzielny przez \(\displaystyle{ 3}\), podobnie dla kwadratu i \(\displaystyle{ 2}\), zatem jeśli \(\displaystyle{ n}\) jest sześcianem i kwadratem, to istnieje taka liczba naturalna \(\displaystyle{ m}\), że \(\displaystyle{ n=m ^{6}}\). Jeśli \(\displaystyle{ 7}\) dzieli \(\displaystyle{ m}\), to oczywiście \(\displaystyle{ n}\) jest postaci \(\displaystyle{ 7 \cdot 7 ^{5} p ^{6}}\) dla \(\displaystyle{ p= \frac{m}{7}}\) , zaś w przeciwnym wypadku, jako że \(\displaystyle{ 7}\) jest liczbą pierwszą, to z MTF \(\displaystyle{ n=m ^{6}\equiv 1\pmod{7}}\). Odpowiedź: TAK.