[ 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: 4210
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: 4210
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 3
Witam, Przeanalizowałem sobie działanie następującego algorytmu: http://www.algorytm.org/algorytmy-arytm ... larne.html...
 freak91  1
 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
 Wyznaczenie macierzy odwrotnej modulo
Dzięki, już rozumiem. Zapomniałem, że dzielenie to mnożenie przez liczbę odwrotną....
 sinnervo  2
 Operacja modulo
Jak policzyc cos takiego najlepiej bez uzycia kalkulatora, choc i z tym nie daje rady. -5988^{26} \pmod{103}...
 Faner  6
 Dowód z przystawaniem modulo
Witam! Mógłbym prosić o jakąś wskazówkę? Podać dowód lub kontrprzykład dla poniższej własności: Dla a, m, k, l \in \mathbb{N} takich, że a^{k} \equiv a^{l} \equiv 1 \pmod{m} zachodzi:[tex:19vv...
 VillagerMTV  4
 zadnko z modulo(jeszcze kilka zadan !!)
kto mi wytlumaczy krok po kroku zadnia z modulo bo moja sorka wcale nietlumaczy a ja nic nie kapuje Wykaż, że jeżeli nεN i n nie jest podzielne przez 3, to n� +2 jest podzielne przez 3 chce cale rozwiazanie od poczatku do konca bo chce miec wzo...
 siurek  9
 Równanie z niewdiaomą w modulo
Jak ugryźć taki układ równań? \begin{cases} 59=\left( 68+k1\right)modN \\ 84=\left( 68+2k1\right)modN \end{cases}...
 pirat_kg  3
 Kongruencja modulo 19
Jak zbudować cechę podzielności przez 19?...
 spzkasia  1
 Liczenie modulo
Witam! Nie mogę znaleźć objaśnienia modulo, w szczególności chodzi o liczenie modulo licz ujemnych i ułamków. Potrzebne są jakieś tabelki, tak? Ale w jaki sposób je wykorzystać? Jak z nich wyczytać, że -2=1(mod 3)...
 meDarq  2
 Kongruencje i działania modulo - dwie tezy do udowodnienia
Witam! Niedawno sorka wprowadziła u mnie w szkole temat kongruencji i działań modulo no i niestety byłem chory i teraz prawie nie rozumiem z tego. Z wiedzą z internetu rozwiązałem kilka zadań, natomaist z poniższymi mam mały problem i proszę o pomoc ...
 necrordian  2
 Arytmetyka dużych liczb: potęgowanie i modulo
Mamy wyrażenie: r = x^{y}\ mod\ n gdzie r,x,y,n\ N\\y\leq10^{10000}\\n\leq 100\\x\leq2^{32} Pytanie, jak naj...
 MGT  0
 Dowód równości modulo
Jesteś pewien, że dobrze przepisałeś treść? Bo po pierwsze b wcale nie musi być odwracalny (np. dla p=3,q=5,b=2 nie istnieje odwrotność 2 modulo 8[/t...
 Stanley1  1
 A do potęgi n modulo 10^9
Witam! Mam liczbę a^{n} i chcę dostać jej modulo z liczby 10^{9}-401. Dodam ,że nie ja ustalam jakie to będą liczby ...
 Domandinho  3
 Potęga modulo - zadanie 2
Jakie x spełniają (a^{31})^x \equiv a \pmod{271} ?...
 lennyh  4
 Układ modulo
Witam proszę o pomoc z takim zadankiem : Rozwiązać układ : \begin{cases} x$\equiv $42 mod 61 \\ x$\equiv $11 mod 12 \end{array}....
 gelo21  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com