Wilson-tétel

A Wilson-tétel a következőt állítja: ha p prímszám, akkor

.

Összetett számra ez nem teljesülhet, mivel, ha n>1 összetett, akkor n-nek és (n-1)!-nak van közös osztója, sőt, minden 4-nél nagyobb n összetett számra

.

Így ez a tétel elméletben használható lenne prímtesztnek, de gyakorlatilag szorzás elvégzésével jár, így a tipikusan legalább pár száz jegyből álló számoknál nem praktikus.

Az angol John Wilson, Edward Waring tanítványa fedezte fel. Waring 1770-ben bejelentette a tételt, de bizonyítani nem tudta. Lagrange adta az első bizonyítást 1773-ban. Minden jel szerint már Leibniz ismerte a tételt, de nem publikálta.[1]

A tételt úgy is általánosíthatjuk tetszőleges modulusra, hogy a redukált maradékosztályok szorzatát vizsgáljuk: ilyenkor a szorzat -1 maradékot ad a modulusra nézve, ha az 4, egy páratlan prímhatvány, vagy egy páratlan prímhatvány kétszerese; minden más esetben a keresett maradék értéke 1.

Bizonyításai

1. bizonyítás

Feltesszük, hogy p>2. Minden x redukált maradékosztályhoz van egy és csak egy y redukált maradékosztály, hogy xy≡ 1 mod p. Ezzel párokra osztom a redukált maradékosztályokat, csak akkor van baj, amikor egy maradékosztály önmagának a párja, azaz x2≡ 1 mod p. Tehát a redukált maradékrendszert fel tudom bontani a következőképpen: 1,-1, és párok, amiknek a szorzata az 1 maradékot adja. Ezeket összeszorozva a -1 maradékot kapjuk.

2. bizonyítás

Feltehetjük, hogy p>2. A modulo p test fölött vegyük a következő polinomot:

Ez a kis Fermat-tétel miatt 0 az 1,…,p-1 maradékosztályok mindegyikére, viszont fokszáma legfeljebb p-2, mert a két xp-1-s tag kiejti egymást. Test feletti polinomok között csak az azonosan 0 polinomnak lehet több gyöke, mint a fokszáma, ez tehát az azonosan 0 polinom. Tehát konstans tagja is nulla, ami (mivel p páratlan) .

3. bizonyítás

Tegyük fel, hogy p>2. Legyen primitív gyök modulo p (ismert, hogy ilyen létezik). Ekkor , hiszen -nek p-1 egymásutáni hatványa redukált maradékrendszert alkot modulo p. Így , itt használtam, hogy p páratlan prím, továbbá, hogy , mert 1 nem lehet, mert g primitív gyök, de négyzete a kis Fermat-tétel miatt, így csak lehet.

A tétel általánosítása

Gauss általánosította a tételt a következő módon.[2] Legyen Π(n) a modulo n redukált maradékrendszer elemeinek szorzata, ekkor Π(n) ≡ -1 mod n, ha n=4, páratlan prímhatvány, vagy páratlan prímhatvány kétszerese, a többi esetben Π(n) ≡ 1 mod n.

Az általánosítás bizonyítása természetes módon átvihető az előbbi 1. bizonyításból:

Világos, hogy minden redukált x maradékosztályhoz pontosan egy olyan y redukált maradékosztály van, amelyre xy ≡ 1 (mod n). Lesznek olyan x maradékosztályok, melyekre x és y különbözik egymástól, ezek a maradékosztályok tehát olyan párokba rendezhetők, melyeknek szorzata modulo n éppen 1 lesz. Vagyis az összes ilyen maradékosztály szorzata is 1-et ad modulo n.

Itt azokat a maradékosztályokat hagytuk ki, melyekre x=y, vagyis x2 ≡ 1 mod n. Ezeknél a maradékosztályoknál párosítsuk össze az x és n-x maradékosztályokat (ezek különbözők, hisz n>2), ez azért hasznos számunkra, mert x(n-x) ≡ -x2 ≡ -1 mod n. Már csak az a feladat, hogy számoljuk össze ezen maradékosztályokat.

Írjuk fel n prímfelbontását: legyen . Ekkor a kínai maradéktétel szerint x2 ≡ 1 mod n ekvivalens azzal, hogy teljesül minden i=1,...,k-ra. Ez pontosan kétféle lehetőséget ad x maradékára modulo , ha , hiszen a kongruencia ekvivalens a oszthatósággal, ahol a két tényező közül legfeljebb egy lehet -vel osztható, vagyis a kongruencia két megoldása . Modulo egy kettőhatvány kicsit más a helyzet: ha , akkor mindkét tényező páros lesz: egyik 4-gyel osztható, a másik nem. Az esetekben rendre 1 és 2 megoldása van a kongruenciának, ám -ra már 4 megoldása van a kongruenciának modulo , hiszen csak -nek kell fennállnia.

Ha az x2 ≡ 1 mod n kongruencia megoldásszáma 4-gyel osztható, akkor páros sok pár jön létre, így a redukált maradékrendszer elemeinek szorzata 1 lesz, ha pedig nem, akkor -1 a szorzat. A megoldásszámot pedig megkaphatjuk, ha összeszorozzuk minden i=1,...,k-ra az megoldásszámát, hisz az modulo az egyes prímhatványok egymástól függetlenül választhatjuk meg x maradékát. Ebből leolvasható, hogy a szorzat 1, ha legalább két 2-nél nagyobb prímtényezője van n-nek, illetve ha osztható 4-gyel és 4-nél nagyobb, továbbá ha nem osztható 4-gyel és legfeljebb egy 2-nél nagyobb prímtényezője van, vagy ha n=4, akkor a szorzat -1 lesz: ezt akartuk belátni.

Jegyzetek

  1. Earliest Known Uses of Some of the Words of Mathematics (W). [2015. április 2-i dátummal az eredetiből archiválva]. (Hozzáférés: 2007. június 28.)
  2. Disquisitiones Arithmeticae, 78. paragrafus.

Read other articles:

Calcio Lecco 1912Calcio Blucelesti, Manzoniani Segni distintivi Uniformi di gara Casa Trasferta Terza divisa Colori sociali Blu, celeste Simboli Aquila, batell[1] Inno Forza LeccoHerman Dati societari Città Lecco Nazione  Italia Confederazione UEFA Federazione FIGC Campionato Serie B Fondazione 1912 Rifondazione2002Rifondazione2016 Proprietario Elettronica Video Games Presidente Cristian Di Nunno[2] Allenatore Alfredo Aglietti Stadio Rigamonti-Ceppi(5 508[3]...

 

Shoot to ThrillLagu oleh AC/DCdari album Back in BlackDirilis25 July 1980Direkam1980GenreHard rockDurasi5:17LabelAtlanticPencipta Angus Young Malcolm Young Brian Johnson ProduserRobert John Mutt Lange Shoot to Thrill merupakan salah satu lagu dari band Rock and Roll asal Australia, AC/DC. Lagu ini merupakan lagu kedua dalam album Back in Black yang dirilis pada 25 Juni 1980.[1] Lagu ini juga merupakan lagu kedua dalam album AC/DC Live[2] dan AC/DC Live (1992, Special Collector...

 

Pour les articles homonymes, voir Dumoustier. Pierre Dumoustier Médaillon représentant le général Dumoustier, passage Pommeraye (Nantes). Naissance 17 mars 1771Saint-Quentin (Picardie) Décès 15 juin 1831 (à 60 ans)Nantes (Loire-Inférieure) Origine Royaume de France Arme Infanterie Grade Général de division Années de service 1793 – 1831 Distinctions Grand officier de la Légion d'honneurOrdre de la Couronne de ferComte de l'Empire Hommages Nom gravé sous l'arc de triomphe d...

Pakistani cricketer SIInzamam-ul-HaqInzamam-ul-Haq in 2005Personal informationFull nameSyed Inzamam-ul-Haq[1]Born (1970-03-03) 3 March 1970 (age 54)Multan, Punjab, PakistanNicknameInzi[2] Sultan of Multan[3]Height6 ft 3 in (191 cm)[4]BattingRight-handedBowlingSlow left-arm orthodoxRoleBatsmanRelationsJaved Ilyas (uncle)[5] Imam-ul-Haq (nephew)Ibtesam-ul-Haq (son)[6]International information National sidePakistan (1991–...

 

Region of Myanmar Region in Lower, MyanmarAyeyarwady Region ဧရာဝတီတိုင်းဒေသကြီးRegionMLC transcription(s) • Burmeseerawa.ti tuing: desa. kri: FlagSealLocation of Ayeyarwady Region in MyanmarCoordinates: 16°50′N 95°10′E / 16.833°N 95.167°E / 16.833; 95.167Country MyanmarRegionLowerCapitalPatheinGovernment • Chief MinisterTin Maung Win • CabinetAyeyarwady Region Government �...

 

Pour les articles homonymes, voir Boston (homonymie). Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (septembre 2021). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». E...

The Oxfordshire MuseumThe entrance to the museumShown within OxfordshireLocationFletcher's House, Park Street, Woodstock, Oxfordshire, EnglandCoordinates51°50′54″N 1°21′26″W / 51.8483°N 1.3572°W / 51.8483; -1.3572Websitewww.oxfordshire.gov.uk/the_oxfordshire_museum The Oxfordshire Museum (also known as Oxfordshire County Museum) is in Woodstock, Oxfordshire, England, located in Fletcher's House, Park Street, opposite the Bear Hotel.[1] It is a regi...

 

Questa voce sull'argomento calciatori spagnoli è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Manuel Clarés Nazionalità  Spagna Calcio Ruolo Attaccante Termine carriera 1980 CarrieraSquadre di club1 1971-1972 Gandía? (?)1972-1974 Castellón63 (22)1974-1978 Barcellona86 (34)1978-1980 Rayo Vallecano47 (9)Nazionale 1973 Spagna1 (0) 1 I due numeri indicano le presenze e le reti...

 

Ini adalah nama Tionghoa; marganya adalah Sze. Sze Hang-yuSze Hang-yu (kiri) di Pesta Olahraga Asia Timur 2009Informasi pribadiNama lengkapRosanna SZE Hang-yuKewarganegaraan Hong KongLahir05 Maret 1988 (umur 36)Tinggi168 m (551 ft 2 in)Berat63 kg (139 pon) (139 pon) OlahragaOlahragaRenangStrokGaya bebas, gaya kupu-kupu Rekam medali Renang putri Mewakili  Hong Kong Pesta Olahraga Asia 2018 Jakarta 4×100 m medley 2018 Jakarta 4×100 m gaya bebas 2018 Jak...

Област Велико ТърновоProvincia de Veliko Tarnovo Provincia Escudo Coordenadas 43°19′00″N 25°33′00″E / 43.316666666667, 25.55Capital Veliko TarnovoEntidad Provincia • País  BulgariaGobernador Toshko NikiforovSubdivisiones 10 municipiosSuperficie   • Total 4.662 km²Población (2006)   • Total 291,121 hab. • Densidad 62,5 hab./km²Huso horario EET (UTC+2) • en verano UTC+3Matrícula BT Siti...

 

UK school that specialises in certain subject areas This article is about specialist schools in the United Kingdom. For specialist schools in other countries, see specialist school. For special needs schools, see special school. A sign for Loreto Grammar School in Altrincham with its specialist status in maths and science advertised. Specialist schools[a] in the United Kingdom (sometimes branded as specialist colleges in England and Northern Ireland) are schools with an emphasis or fo...

 

National kabaddi team of India This article is about the men's team. For the women's team, see India women's national kabaddi team. IndiaAssociationAmateur Kabaddi Federation of India (AKFI)RegionAsian Kabaddi Federation (AKF)Head coachBhaskaran EdacheryCaptainPawan SehrawatAffiliation(s)International Kabaddi Federation (IKF)WebsiteIndian Kabaddi Federation The India men's national kabaddi team represents India in international men's kabaddi competitions. The team is by far the most successfu...

British statistician (born 1946) Sir Adrian SmithPRS63rd President of the Royal SocietyIncumbentAssumed office 30 November 2020Preceded byVenki Ramakrishnan Personal detailsBornAdrian Frederick Melhuish Smith (1946-09-09) 9 September 1946 (age 77)Dawlish, Devon, EnglandResidenceUKAlma materUniversity of CambridgeUniversity College LondonAwardsGuy Medal (Bronze, 1977) (Silver, 1993) (Gold, 2016)Scientific careerFieldsStatisticsInstitutionsImperial College London Queen Mary, U...

 

كافار Gavar  شعار الاسم الرسمي GavarԳավառ الإحداثيات 40°21′32″N 45°07′36″E / 40.35889°N 45.12667°E / 40.35889; 45.12667 تاريخ الإنشاء 18301850 تقسيم إداري  بلد  أرمينيا  محافظات أرمينيا محافظة غغاركونيك عاصمة لـ محافظة كغاركونيك  الحكومة  رئيس البلدية جورجن مارتيروسيان خصائ...

 

Islamic state in West and Central Africa (1809–1903) Adamawa Emirateإمارة أداماوة‎Lamorde Adamaawaلَمࣷرْدٜ عَدَمَاوَ‎ / 𞤤𞤢𞤥𞤮𞤪𞤣𞤫 𞤢𞤣𞤢𞤥𞤢𞥄𞤱𞤢1809–1903 FlagAdamawa Emirate (right) in the orbit of the Sokoto Caliphate .StatusEmirate of the Sokoto CaliphateCapital Gurin (1809-1831) Ribadu (1831-1839) Njoboliyo (1839-1841) Yola (1841) GovernmentMonarchy• Lamido Fombina Modibbo Adama• Galadima Sambo...

Mammalian protein found in Homo sapiens ACTR2Available structuresPDBOrtholog search: PDBe RCSB List of PDB id codes2P9N, 1TYQ, 1U2V, 4JD2, 3DXK, 3UKU, 3UKR, 2P9P, 2P9U, 3ULE, 3RSE, 2P9S, 2P9I, 4XF2, 2P9L, 1K8K, 3DXM, 4XEIIdentifiersAliasesACTR2, ARP2, ARP2 actin-related protein 2 homolog (yeast), ARP2 actin related protein 2 homolog, actin related protein 2External IDsOMIM: 604221; MGI: 1913963; HomoloGene: 4181; GeneCards: ACTR2; OMA:ACTR2 - orthologsGene location (Human)Chr.Chromosome 2 (hu...

 

This article is part of a series on thePolitics of the People's Republic of Bangladesh Constitution Amendments Law of Bangladesh Bangladesh Code Penal Code Human rights Article 70 Judicial review Government President: Mohammed Shahabuddin Prime Minister: Sheikh Hasina Cabinet: Hasina V Taxation Agencies Civil Service Local governments Parliament Speaker: Shirin Sharmin Chaudhury Leader of the House: Sheikh Hasina Leader of the Opposition: GM Quader Judiciary Supreme Court: Appellate Division ...

 

الأشمونين  -  قرية مصرية -    تقسيم إداري البلد  مصر[1] التقسيم الأعلى مركز ملوي  المسؤولون خصائص جغرافية إحداثيات 27°46′28″N 30°48′04″E / 27.774438888889°N 30.801111111111°E / 27.774438888889; 30.801111111111   الارتفاع 44 متر[2]  معلومات أخرى التوقيت ت ع م+02:00  الرمز...

Cet article est une ébauche concernant l’histoire, l’Allemagne et le nazisme. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Château de la famille Moltke à Kreisau. Le cercle de Kreisau a été l'un des éléments de la résistance allemande au nazisme. Il provient du nom du château de Kreisau de la famille von Moltke en Silésie (aujourd'hui Krzyżowa). Ce cercle fut actif de 1938 à 1944. Le nom «...

 

Find a Grave网站类型在线数据库语言英语持有者吉姆·蒂普顿创始人吉姆·蒂普顿网址www.findagrave.com商业性质盈利注册可选推出时间1995年,​29年前​(1995)现状運作中 位于犹他州普若佛的总部 Find a Grave是一个提供全球墓葬信息数据库服务的盈利性网站,由美國猶他州鹽湖城人吉姆·蒂普顿(Jim Tipton)创建。 历史 据网站创建者,盐湖城居民吉姆·蒂普顿[1]所述�...