mod 7019801

buliin · Post autor: **buliin** » 17 sty 2008, o 14:32

Mam takie zadanie, nie mam pojęcia jak je rozwiązać...

Dowieść, że \(\displaystyle{ 10 ^{50} +1 \equiv 0 (mod 7019801)}\)

Ktoś może wie jak to zrobić?

Xitami · Post autor: **Xitami** » 21 sty 2008, o 18:18

\(\displaystyle{ 14245418068119025026492916252184356793020201\cdot 7019801=10^{50}+1}\)

buliin · Post autor: **buliin** » 21 sty 2008, o 22:19

hmm... Nieco "bolesne" rozwiązanie, nie da się prościej?

Xitami · Post autor: **Xitami** » 21 sty 2008, o 22:51

\(\displaystyle{ 101\cdot60101\cdot3541\cdot27961\cdot23702464296258769770591950101\cdot7019801=10^{50}+1}\)

Piotr Rutkowski · Post autor: **Piotr Rutkowski** » 21 sty 2008, o 22:52

Xitami, czy dałbyś radę rozbić 7019801 na czynniki pierwsze? Być może to umożliwi jakiś znośny dowód

Szemek · Post autor: **Szemek** » 21 sty 2008, o 22:56

7019801 - liczba pierwsza
przynajmniej tak pokazuje Mathematica

Xitami · Post autor: **Xitami** » 22 sty 2008, o 01:00

23702464296258769770591950101 tyż jest pierwsze

scyth · Post autor: **scyth** » 22 sty 2008, o 01:14

Na ile minut bylo to zadanie?

buliin · Post autor: **buliin** » 22 sty 2008, o 13:37

To na szczęście nie zadanie z konkursu Co nie zmienia faktu, że rozwiązanie Xitami jest (przynajmniej jak dla mnie;) dość ...hmm... czasochłonne Liczyłem na coś bardziej oczywistego, bez takich ogromniastych mnożeń. Zazwyczaj najprostsze rozwiązania są pod nosem i myślałem, że po prostu nie umiem go dostrzec Na mnożenie tego wszystkiego to chyba nie mam takiej dużej kartki :-D

mroman · Post autor: **mroman** » 26 sty 2008, o 15:18

Nie wiem czy dobrze myślę i czy tak można:

\(\displaystyle{ 10 ^{50} \equiv -1 \mod 7019801}\)
ponieważ 7019800/50=140396, więc podnosimy do tej potęgi obie strony. z malego tw. fermata wychodzi.
Napiszcie czy jest ok.

Post autor: **Ponewor** » 24 maja 2012, o 18:10

Wyjaśni ktoś co miał na myśli kolega wyżej?

leapi · Post autor: **leapi** » 24 maja 2012, o 21:38

chodziło mu o to
\(\displaystyle{ 10^{50}\equiv 1 \mod 7019801}\)

\(\displaystyle{ \left( 10^{50}\right)^{140396} \equiv 1^{140396} \mod 7019801}\)

\(\displaystyle{ 10^{50\cdot 140396}\equiv 1 \mod 7019801}\)

\(\displaystyle{ 10^{7019800}\equiv 1 \mod 7019801}\)

co zachodzi na mocy małego tw fermata \(\displaystyle{ a^{p-1}\equiv 1 \mod p}\)

Vax · Post autor: **Vax** » 24 maja 2012, o 21:40

Ale to nie są przejścia równoważne, więc ten ,,dowód" jest niepoprawny.

Post autor: **Ponewor** » 26 maja 2012, o 11:46

bo w drugą stronę musiałby pierwiastkować kongruencję?

Vax · Post autor: **Vax** » 26 maja 2012, o 11:55

Tak, w ogólności nie można pierwiastkować kongruencji.