Share to: share facebook share twitter share wa share telegram print page

互いに素 (整数論)

二つの整数 a, b互いに素(たがいにそ、: coprime, relatively prime, prime to[1])であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b最大公約数 gcd(a, b)1 であることと同値である。a, b が互いに素であることを、記号で a b と表すこともある[2]。なお、「互いに素」を意味する英単語には coprimedisjoint があるが、coprime は整数について「互いに素」「共通点を持たない」という意味で使用される。

概要

例えば、310 を共に割り切る正の整数は 1 だけなので、これらは互いに素である。逆に、36 は共に 3 で割り切れるので、これらは互いに素ではない。もう少し大きい数だと、7291000 を共に割り切る正の整数は 1 だけなので、これらは互いに素である。逆に、7291296392781 の四つで割り切れるので、この二つは互いに素ではない。同じく、10001296 も、248 の三つで割り切れるので、この二つも互いに素ではない。

互いに素であることの判定は素因数分解を用いて行うこともできるが、二つの整数のうち少なくとも一方が巨大である場合など一般には困難である。素因数分解によって公約数を調べる方法よりも、ユークリッドの互除法によって最大公約数を調べる方法のほうが遥に速い。

正の整数 n と互いに素となる(1 から n の間の)整数の個数は、オイラー関数 φ(n) によって与えられる。

三つの整数 a, b, c互いに素であるとは、gcd(a, b, c) = 1 が成り立つことをいう。また、gcd(a, b)gcd(b, c)gcd(c, a) がすべて 1 に等しいとき、a, b, c対ごとに素: pairwise coprime)またはどの二つも互いに素であるという。一般に、互いに素であるからといって対ごとに素であるとは限らない  (例:a = 6, b = 15, c = 10)。一般の n 個の整数についても同様に定義される。

性質

  • 0 と互いに素となる整数は 1−1 だけであり、また任意の整数と互いに素となる整数も 1−1 だけである。
  • 異なる二つの素数は互いに素であり、連続する二つの整数も互いに素である。
  • 2 以上の整数は、その(自身を含む)倍数2 以上の約数と互いに素でない。
  • ab1ab2 がそれぞれ互いに素ならば、ab1b2 も互いに素である。

以下は、整数 a, b が互いに素であることと同値な条件である。

  • a, b を共に割り切る素数が存在しない。
  • ax + by = 1 を満たす整数 x, y が存在する。(ベズーの等式を参照)
  • ba法とする逆数をもつ。即ち by ≡ 1 (mod a) を満たす整数 y が存在する。別の言い方をすれば、ba を法とする剰余類環 Z/aZ単元となっている。
  • a, b最小公倍数 lcm(a, b) が積 ab に等しい。
  • a, b最大公約数 gcd(a, b)1 に等しい。
  • 2a − 12b − 1 が互いに素。

互いに素である確率

整数の中から任意に選んだ2つの数 ab が互いに素である確率を、ナイーブには、以下のように求めることができる。

ab が互いに素とは、任意の素数 p に対して、ab の少なくとも一方が p の倍数でないこと、と言い換える。

p を固定したとき、この事象は、a, b がともに p の倍数である事象の余事象である。

ap の倍数である確率は 1/p である。(b についても同様)

p に対して、これらの試行は独立だから、求める確率は、

[3]

ここで、ζリーマンのゼータ関数を表す。ζ(2) の値レオンハルト・オイラーによって求められた。一般に、任意に選んだ k 個の整数が互いに素である確率は 1/ζ(k) で表される。

互いに素な整数の組の生成

このアルゴリズムによる互いに素な組の生成の順番。最初のノード (2, 1) を赤、その三つの子ノードを橙、さらにその子ノードを黄色で示し、それ以降を虹色の順に色を用いて示した。

すべての互いに素な正の整数の組 (m, n)(ただし m > n)は、二つの互いに素な完全三分木英語版を用いて並べることができる。片方の木は (2, 1) から始まり偶数・奇数および奇数・偶数の組を[4]、もう片方は (3, 1) から始まり奇数・奇数の組を[5]生成する。このときノード (m, n) から生成される三つの子ノードはそれぞれ次のように表される。

  1. (2mn, m)
  2. (2m + n, m)
  3. (m + 2n, n)

以上により生成される組は常に互いに素であり、すべての組が重複なく網羅される。

実用、応用

  • 固定ギア自転車の理想的なスキッドポイントの設計 - 固定ギアの自転車のチェーンリングとコグの歯数が「互いに素」であると、スキッドポイントと呼ばれるタイヤが摩耗する点はコグの歯数と同じになる。

脚注

参考文献

  • Baker, Alan (1984). A Concise Introduction to the Theory of Numbers. Cambridge University Press. ISBN 0-521-28654-9 
  • Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics, Addison-Wesley 
  • Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the Pythagorean triplets revisited", Mathematical Gazette, 78: 190–193, doi:10.2307/3618576
  • Mitchell, Douglas W. (July 2001), “An alternative characterisation of all primitive Pythagorean triples”, Mathematical Gazette 85: 273–275, doi:10.2307/3622017 

関連項目

Read more information:

Священная роща Балта-Тиймез Вид на Иосафатову долину со стен Чуфут-Кале. Роща находится среди сплошного лесостоя более молодого возраста Категория МСОП — III (Памятник природы)Основная информация Площадь2,3 га  Средняя высота20—30 м Дата основания21 декабря 2011 года  У

2011 FIFA Women's World CupFIFA Frauen-Weltmeisterschaft Deutschland 2011Tournament detailsHost countryGermanyDates26 June – 17 JulyTeams16 (from 6 confederations)Venue(s)9 (in 9 host cities)Final positionsChampions Japan (1st title)Runners-up United StatesThird place SwedenFourth place FranceTournament statisticsMatches played32Goals scored86 (2.69 per match)Attendance845,711 (26,428 per match)Top scorer(s) Homare Sawa (5 goals)Best player(s) Homar…

George MacKayMacKay pada Festival Film Internasional Toronto 2013PekerjaanAktorTahun aktif2003-sekarang George MacKay (lahir 13 Maret 1992) adalah aktor asal Inggris. Ia berperan sebagai Riccio dalam film The Thief Lord serta berperan sebagai Schofield dalam film 1917 Biografi MacKay lahir di London, Inggris. Filmografi Peter Pan (2003) sebagai Curly Rose and Maloney as Young Calum (1 episode, 2004) Footprints in the Snow (2005) (TV) as Nathan Hill The Thief Lord (2006) sebagai Riccio Johnn…

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Junho de 2012) Si maior Notação Tonalidade Relativa Dó bemol maior Homónima Si menor Modo Modo maior, tonalidade Notas componentes Si, Dó♯, Ré♯, Mi, Fá♯, Sol♯, Lá♯, Si Na música, Si maior (abreviatura …

Cet article est une ébauche concernant une équipe nationale de football et le Ghana. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Équipe du Ghana de football à la Coupe du monde 2014 Fédération GFA Classement 25e (premier tour) Organisateur(s) Brésil Participation 3e Meilleure performance 7e (quart de finale) en 2010 Sélectionneur James Kwesi Appiah Capitaine Asamoah Gyan Meilleur buteur André Ayew et As…

نهر تشي مانوك   المنطقة البلد إندونيسيا  الخصائص المصب بحر جاوة  تعديل مصدري - تعديل   نهر تشي مانوك (بالإندونيسية: Ci Manuk، يعني: نهر الطيور باللغة السوندية)‏ هو نهر في جاوة الغربية بإندونيسيا،[1] الأجزاء الكاملة من هذا النهر تقع داخل مقاطعة جاوة الغربية. يمتد النه

Verwaltung US-Bundesstaat: Maine Verwaltungssitz: Dover-Foxcroft Gründung: 23. März 1838 Demographie Einwohner: 16.800 (Stand: 2020) Bevölkerungsdichte: 1,64 Einwohner/km2 Geographie Fläche gesamt: 11.337 km² Wasserfläche: 1065 km² Karte Karte von Piscataquis County innerhalb von Maine Piscataquis County[1] ist ein County im Bundesstaat Maine der Vereinigten Staaten. Piscataquis County ist der Teil von Maine mit der geringsten Bevölkerungsdichte. Der Sitz der Count…

artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahka…

RushAlbum studio karya RushDirilis1 Maret 1974DirekamAwal-1973 (sesi awal) dan November 1973 (sesi akhir)[1] Eastern Sound Studios, Toronto, KanadaGenreBlues rock, hard rockDurasi39:51LabelMoon RecordsProduserRushKronologi Rush Rush(1974) Fly by Night(1975)Fly by Night1975 Rush adalah album debut band asal Kanada Rush, dirilis pada tahun 1974 dan remaster pada tahun 1997. Rilis pertama mereka menunjukkan banyak suara khas hard rock dari banyak band rock populer yang muncul dari Inggr…

Tugu Kartini Tugu Kartini adalah sebuah tugu atau monumen yang sering dipakai sebagai simbol atau lambang dari kota Jepara.[1] Tugu ini terletak di tengah persimpangan Jalan dengan sebelah Utara Jl. RA. Kartini, sebelah Timur Jl. Pemuda, Selatan Jl. K.S. Tubun, dan sebelah Barat Jl. Cokroaminoto. Tugu Kartini yang berbentuk Patung R.A Kartini dengan tangan kanan memegang obor menjulang tinggi dan tangan kiri menggandeng seorang gadis dengan ditangan kiri gadis itu memegang sebuah buku. T…

العلاقات الإماراتية الميكرونيسية الإمارات العربية المتحدة ولايات ميكرونيسيا المتحدة   الإمارات العربية المتحدة   ولايات ميكرونيسيا المتحدة تعديل مصدري - تعديل   العلاقات الإماراتية الميكرونيسية هي العلاقات الثنائية التي تجمع بين الإمارات العربية المتحدة وو

United States Army general Robert Nicholas YoungYoung as commander of the United States Infantry SchoolBorn(1900-01-14)January 14, 1900Washington, D.C.DiedOctober 19, 1964(1964-10-19) (aged 64)Asheville, North CarolinaBuriedArlington National CemeteryAllegianceUnited StatesService/branchUnited States ArmyYears of service1923–1957RankLieutenant GeneralCommands heldSixth United States ArmyUnited States Army Infantry School2nd Infantry DivisionCombined Arms CenterMilitary District of Wa…

Irish young adult novel series This article is about the complete series. For the first book with the same title, see Skulduggery Pleasant (novel). Skulduggery PleasantThe covers of the Skulduggery Pleasant books. First series: Skulduggery Pleasant Playing with Fire The Faceless Ones Dark Days Mortal Coil Death Bringer Kingdom of the Wicked Last Stand of Dead Men The Dying of the Light Second series: Resurrection Midnight Bedlam Seasons of War Dead or Alive Until the End Third series: A Mind Ful…

1930 film The Rogue SongLobby cardDirected byLionel BarrymoreHal Roach (uncredited)Screenplay byJohn Colton Frances MarionWells Root (suggested by)Based onGipsy Loveby Franz LehárProduced byIrving ThalbergStarringLawrence TibbettStan LaurelOliver HardyCinematographyPercy Hilburn (*French)Charles Edgar Schoenbaum(Technicolor)Edited byMargaret BoothMusic byHerbert Stothart Franz Lehár Clifford GreyDimitri Tiomkin (ballet)[1]ProductioncompanyMetro-Goldwyn-MayerDistributed byLoew's, Inc.Re…

Bilateral relationsRussian-Nicaraguan relations Russia Nicaragua Embassy of Nicaragua in Moscow Nicaragua–Russia relations are the bilateral relations between Russia and Nicaragua. History Nicaragua first recognized the Soviet Union on 18 November 1944.[1] Agreements to open diplomatic missions were signed on October 18, 1979, between Nicaragua and the Soviet Union a few months after the Sandinista revolution.[2] Russia is the sole successor to the Soviet Union, so ties have na…

2013 film directed by James Ponsoldt The Spectacular NowTheatrical release posterDirected byJames PonsoldtScreenplay by Scott Neustadter Michael H. Weber Based onThe Spectacular Nowby Tim TharpProduced by Tom McNulty Shawn Levy Michelle Krumm Andrew Lauren Starring Miles Teller Shailene Woodley Brie Larson Mary Elizabeth Winstead Bob Odenkirk Jennifer Jason Leigh Kyle Chandler CinematographyJess HallEdited byDarrin NavarroMusic byRob SimonsenProductioncompanies Andrew Lauren Productions 21 Laps …

Subgroup of the Austroasiatic language family AslianGeographicdistributionPeninsular Malaysia and Southern ThailandLinguistic classificationAustroasiaticAslianProto-languageProto-AslianSubdivisions Jahaic Senoic Southern Jah Hut Shompen (possibly) Glottologasli1243  Aslian The Aslian languages (/ˈæsliən/) are the southernmost branch of Austroasiatic languages spoken on the Malay Peninsula. They are the languages of many of the Orang Asli, the aboriginal inhabitants of the peninsula.…

Swedish poet, writer and humourist Nils Hasselskog. Nils Hasselskog (1892–1936) was a Swedish poet, writer and humourist. He debuted as a writer for Grönköpings Veckoblad in 1925.[1] Hasselskog's years at the magazine are considered its artistic peak.[2] He was the creator of the parody language Transpiranto. References ^ Kylhammar, Martin; Nilsson, Göran B (1987). Humoristen som humanist. Tvärsnitt (3:87). Retrieved 2009-03-21. ^ Åberg, Martin (2006). Politikern i svensk …

American economist Dr. Harlow S. Person (Image source: Rural Electrification News, U.S. Department of Agriculture, Rural Electrification Administration, June-July 1953, p. 4) Harlow Stafford Person (February 16, 1875 – November 7, 1955)[1] was an American economist, Professor of Management and first Dean at the Amos Tuck School of Business, and later secretary and key figure in the Taylor Society.[2] Biography Youth, education and early career Person was born in Republican City…

American sports card manufacturer This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Pinnacle Brands – news · newspapers · books · scholar · JSTOR (October 2022) (Learn how and when to remove this template message) Pinnacle Brands, Inc.TypePrivateIndustryCollectableFounded1988Defunct1998; 25 years ago…

Kembali kehalaman sebelumnya

Lokasi Pengunjung: 3.236.214.123