fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Prímtesztelés, tanúk?

Prímtesztelés, tanúk?

Figyelt kérdés

Azt akarjuk kideríteni, hogy K prmíszám-e. Ha minden igaz, akkor nevezzük A számot tanúnak, hogyha (A, K)=1 és A^(K-1) nem kongruens 1-gyel mod K. Ha kongruens, akkor nem tanú.

Ha egy K-hoz tartozó nem tanúk halmazából injektíven képezzük a tanúk halmazát úgy, hogy megszorozzuk az elemeket A-val, akkor elvileg a nem tanúk halmazának elemszáma kisebb egyenlő, mint a tanúk halmazának elemszáma. Én ezt azért nem értem, mert pl. K=7-nél, van 6 db nem tanú (1,..,6), ha ezeket egyesével megszorozzuk önmagukkal, akkor pl. az 1^2 és a 2^2-nal mi lesz? Ők így nem tanúk. Aztán hogyha tovább tovább hatványozunk, lesz négy szám a tanúk halmazában, ami kisebb, mint a nem tanúk halmazának elemszáma. :(

Valaki tud ebben segíteni?



#egyetem #matematika #tanú #számelmélet #prímtesztelés
2021. jan. 7. 14:25
1 2 ❯
 1/12 anonim ***** válasza:
75%
Az (1,...,6) miért a nem tanúk halmaza?
2021. jan. 7. 14:37
Hasznos számodra ez a válasz?
 2/12 A kérdező kommentje:
1-től 6-ig igaz az, hogy A^6 kongruens 1-gyel mod 7. És ha jól tudom, ettől nem tanú egy A.
2021. jan. 7. 14:40
 3/12 anonim ***** válasza:

Igazad van. Valamiért azt hittem, hogy ezek nem adnak 1 maradékot 7-tel.

Lehet, hogy én értek valamit félre, de a „megszzorozzuk A-val” nem azt jelenti, hogy mindegyik számot ugyanazzal az A számmal szorozzuk? Tehát nem négyzetre emelünk, hanem mondjuk mindenkit 2-vel szorzunk.

2021. jan. 7. 14:56
Hasznos számodra ez a válasz?
 4/12 A kérdező kommentje:
Erre én is gondoltam, csak akkor mi az az A? Mert egy random A-val szorozva, pl amit mondasz is, hasonló jön ki, mintha négyzetre emelnénk. De igazából a nem tanúk halmazában is A-k vannak, meg A-val is szorzunk elvileg, szóval csak nem használtuk kétszer ugyanazt a jelölést másra. :( De ha mégis így történt véletlen, akkor sem tudom sajnos, hogy mivel kéne szorozni.
2021. jan. 7. 15:07
 5/12 anonim ***** válasza:

Annyi a titok, hogy nem A-val szorzol, hanem K-val.


Legyen adott egy K szám.

Legyenek ekkor a tanúk halmaza: A = {A1,A2,A3,....} (Nem feltétlenül véges halmaz)

Jelöljük továbbá a nem tanúk halmazát B-vel.

A megfelelő leképezés: f: A --> B, f(An) = K*An.

Miért? Mert K*An biztos, hogy nem lesz K-val relatív prím.

Ez egy injekció a tanúk halmazából a nem tanúk halmazába.

Magyarán a tanúk halmazának számossága biztosan kisebb egyenlő, mint a nem tanúké.

2021. jan. 7. 16:04
Hasznos számodra ez a válasz?
 6/12 A kérdező kommentje:
De nem feltétele a nem tanúságnak, hogy A és K relatív prímek legyenek? Hogy fel tudjuk írni az Euler-Fermat tételt, hogy igaz-e?
2021. jan. 7. 16:19
 7/12 anonim ***** válasza:
Jaaa, bocs, azt hittem, hogy az a feltétel a nem tanúra nem vonatkozik.
2021. jan. 7. 16:29
Hasznos számodra ez a válasz?
 8/12 anonim ***** válasza:
Azt akarod éppen bizonyítani, hogy ha K nem prim, akkor “elég sok” tanú van?
2021. jan. 7. 19:33
Hasznos számodra ez a válasz?
 9/12 A kérdező kommentje:

Háát, szerintem nem, vagy lehet, hogy ezt is jelenti. Ez van a füzetemben, ezt szeretném megérteni:

[link]

Itt végülis nincs bizonyítás, csak nem tudom, hogy mi miért van. (Leginkább a halmazok számosságára értem.)

2021. jan. 7. 19:53
 10/12 A kérdező kommentje:
Mert ugye próbáltam rá példát nézni a definíciók alapján, de nem jött ki a reláció.
2021. jan. 7. 19:57
1 2 ❯

További kérdések:

Közoktatás, tanfolyamok főkategória kérdései »
Közoktatás, tanfolyamok - Házifeladat kérdések kategória kérdései »



Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!