[ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 maja 2008, o 11:38 
Użytkownik

Posty: 5
Lokalizacja: abc
czesc. mam takie (chyba) proste pytanie, a cos nie moge znalezc
w necie odpowiedzi

niech a , n - liczby naturalne > 0
p - liczba pierwsza

czy prawda jest, ze


a^n [ mod p ] = a ^ (n mod p) [ mod p ]

innymi slowy, czy moge sobie wykladnik wziac mod p
a nastepnie podniesc a do takiej potegi ..
czy to jest prawda? jesli tak, to jak to udowodnic?
z gory bardzo dziekuje za pomoc :)
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2008, o 11:49 
Użytkownik

Posty: 4260
Lokalizacja: Kraków
Jesli r jest reszta z dzielenia n przez p, to a^n -a^r jest podzielne przez p, to wynia z małego tw Fermata. , o ile a nie dzieli sie przez p.
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2008, o 12:30 
Użytkownik

Posty: 5
Lokalizacja: abc
mol_ksiazkowy napisał(a):
Jesli r jest reszta z dzielenia n przez p, to a^n -a^r jest podzielne przez p, to wynia z małego tw Fermata. , o ile a nie dzieli sie przez p.


hmm..to jest prawda? a jesli n = p

to wg Ciebie a^p - a^0 jest podzielne przez p ?
z tego wynika , ze

a^p = a ^0 [ mod p ]

a tw. fermata mowi chyba , ze :

a ^ (p-1) = a ^ 0 [ mod p ]
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2008, o 13:12 
Użytkownik

Posty: 4260
Lokalizacja: Kraków
ah słusznie, np a=2, p=3 , n=5
a^5 \neq a^2 \ mod \ p
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2008, o 13:33 
Użytkownik

Posty: 5
Lokalizacja: abc
mol_ksiazkowy napisał(a):
ah słusznie, np a=2, p=3 , n=5
a^5 \neq a^2 \ mod \ p


popraw jesli sie myle, ale wydaje mi sie, ze jak bede bral

n mod (p-1)

to juz bedzie ok. tzn bedzie zachodzic:

a ^ (n mod (p-1)) [ mod p ] = a ^ n [ mod p ]
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 potęgowanie modulo - zadanie 2
a^1=3\\ a^6=a^3*a^3=728\equiv8\\ 3^{75}(\equiv24\mod103) minimalna liczba mnożeń Wynik jest dobry, w kwestii formalnej: [tex:vbxjwjl...
 FEMO  5
 Potęgowanie modulo - zadanie 3
Witam, Przeanalizowałem sobie działanie następującego algorytmu: http://www.algorytm.org/algorytmy-arytm ... larne.html...
 freak91  1
 równania modulo
Wie ktoś jak to zrobić (nie zgadnąć) ? \begin{cases} x \equiv 2 (mod 3) \\ x \equiv 3 (mod 5) \end{cases} \begin{cases} x \equiv 3 (mod 7) \\ x \equiv 0 (mod 4)\\ x \equiv ...
 kolotek  1
 Równanie modulo, algorytm Euklidesa
Czy poniższy przykłada jest prawidłowo zapisany ? Oblicz \ 5x \ mod \ 8=1 5x \ mod \ 8=1 \\ 5x \equiv 1(mod \ 8) \\ x \equiv 5 ^{-1}(mod \ 8) \\ \\ Algorytm \ Euklidesa \\ \\ 8/5=1 \ reszty...
 croonx  0
 potęgowanie modularne
Czy może mi ktoś dokładnie wyjaśnić, krok po kroku, jak obliczyć np. a). 13^{101} \ mod \ 16 b). 22^{2011} \ mod \ 13 korzystając z twierdzenia Eulera, tzn.: Dla dowolnych a,m\in...
 patricia__88  6
 Potega modulo
witam, 2^{13}\equiv x \pmod{17} dlaczego odp. to 15 z tw. Eulera \varphi(17)=16 czyli wiem, że 2^{16}\equiv 1 \pmod{17}/ \cdot (2^{3}&#41...
 karl153  1
 Potęgowanie liczb
Mamy takie równanie. X^{X} = Y^{Y} przy czym: X nierówne Y Może ktoś znajdzie wartość(ci) LICZBOWE z uzasadnieniem tego równania....
 Longines  22
 modulo wysokiej potegi
Witam mam takie zadanko do zrobienia, niestety nie mam pojecia jak to sie robi i z czego korzysta. Prosilbym nie tylko o rozwiazanie ale i wytlumaczenie. Z gory dzieki i pozdro Oto zadanie: 6 ^{4521} mod 17[/tex:...
 Xadus  1
 podzielność z użyciem modulo
Udowodnij podzielność przy użyciu przystawania modulo 7|2^{n+2}+3^{2n+1} byłby ktoś taki miły i pokazał jak się robi zadanie tego typu ?...
 manduka  6
 Równanie modulo - zadanie 2
a tego, że 13=4 \cdot 4+1 to nie kumam. błąd po prostu??...
 bluerek  5
 wykaż że 9 do potęgi jest podzielne (potęgowanie modularne)
Wykaż, że: 9^{11 ^{21}} jest podzielne przez 13. Próbowałam zrobić to zadanie już kilka razy i za każdym razem wychodziło źle, może ktos pomoże zrobic i przy okazji wytłumaczy jak rozwiązywać tego typu zadania....
 kesi  1
 Rozpisanie modulo
Cześć! Czy mogę prosić o sprawdzenie, czy dobrze rozpisałam modulo w poniższych równaniach(zwłaszcza w drugim)? 5^n=(6-1)^n=(-1)^n=(-1)^n(mod6) 2 ^{b-1} -1 = (5-3) ...
 PaulinaAnna  2
 Modulo z liczby ^-1
tak myślałem ale nie wiem jakie liczby podstawić w algorytmie Euklidesa do n i m ?...
 gucio1016  5
 Modulo liczby do minusowej potęgi.
Ile to będzie 17^{-3}=x(mod 31) i jak się wylicza modulo liczby do minusowej potęgi? -- 12 lut 2011, o 13:39 -- Widzę, że nikt mi nie pomoże, to proszę chociaż o sprawdzenie: 17^{-3}=x(mod 31&#...
 Michalgromadzki  4
 Wyznaczenie odwrotności X w ciele modulo N
Czesc. Mam taki problem, ze chcialbym znalezc odwrotność X w ciele modulo N. Szukam jakiegos efektywnego sposobu, ktory daloby sie zaimplementowac....
 author  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com