Простой множитель

Это изображение демонстрирует нахождение простых множителей числа 864. Сокращённый способ написания — 25 × 33

В теории чисел, простые множители (простые делители) положительного целого числа — это простые числа, которые делят это число нацело (без остатка)[1]. Выделить простые множители положительного целого числа означает перечислить эти простые множители вместе с их кратностями. Процесс определения простых множителей называется факторизацией целых чисел. Основная теорема арифметики утверждает, что любое натуральное число можно представить в виде единственного (с точностью до порядка следования) произведения простых множителей[2].

Чтобы сократить выражение, простые множители часто представляются в виде степеней простых чисел (кратностей). Например

в котором множители 2, 3 и 5 имеют кратности 3, 2 и 1, соответственно.

Для простого множителя р числа n кратность числа p — это наибольший из показателей степени а, для которых ра делит n нацело.

Для положительного целого числа n, количество простых множителей n и сумма простых множителей n (без учёта кратности) — это примеры арифметических функций из n (аддитивных арифметических функций[фр.][3]).

Полный квадрат

Квадрат числа имеет то свойство, что все его простые множители имеют чётные кратности. Например, число 144 (квадрат 12) имеет простые множители

В более понятной форме:

Поскольку каждый простой множитель присутствует здесь чётное число раз, исходное число можно представить в виде квадрата некоторого числа. Таким же образом, куб числа — это число, у которого кратности простых множителей делятся на три, и так далее.

Взаимно простые числа

Положительные целые числа, не имеющие общих простых множителей, называются взаимно простыми. Два целых числа a и b можно назвать взаимно простыми, если их наибольший общий делитель НОД(a, b) = 1. Если для двух целых чисел неизвестны их простые множители, то для определения того, являются ли они взаимно простыми, используется алгоритм Евклида; алгоритм выполняется за полиномиальное время по количеству цифр.

Целое число 1 является взаимно простым для любого положительного целого числа, включая само себя. Иными словами, число 1 не имеет простых множителей, оно — empty product. Это означает, что НОД(1, b) = 1 для любого b ≥ 1.

Криптографические приложения

Определение простых множителей числа — это пример задачи, которая часто используется для обеспечения криптографической защиты в системах шифрования[4]. Предполагается, что эта задача требует супер-полиномиального времени по количеству цифр. Это значит, что относительно легко сконструировать задачу, решение которой заняло бы больше времени, чем известный возраст Вселенной при текущем развитии компьютеров и с помощью современных алгоритмов.

Функции Омега

Функция ω(n) (омега) представляет собой число различных простых множителей n, в то время как функция Ω(n) (большая Омега) представляет собой число простых множителей n, пересчитанное с учётом кратности[2]. Если

тогда

Например, 24 = 23 × 31, Так что ω(24) = 2 и Ω(24) = 3 + 1 = 4.

  • ω(n) для n = 1, 2, 3, … соответственно 0, 1, 1, 1, 1, 2, 1, 1, 1, … — последовательность A001221 в OEIS.
  • Ω(n) для n = 1, 2, 3, … соответственно 0, 1, 1, 2, 1, 2, 1, 3, 2, … — последовательность A001222 в OEIS.

См. также

Ссылки

  1. Jensen, Gary R. Arithmetic for Teachers: With Applications and Topics from Geometry (англ.). — American Mathematical Society, 2004.
  2. 1 2 Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9
  3. Melvyn B. Nathanson. Additive Number Theory: the Classical Bases (англ.). — Springer-Verlag, 1996. — Vol. 234. — (Graduate Texts in Mathematics). — ISBN 0-387-94656-X.
  4. Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. Handbook of Applied Cryptography (неопр.). — CRC Press, 1996. — ISBN 0-8493-8523-7. Архивировано 7 марта 2005 года.

Read other articles:

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Agustus 2017. Armando Soriano adalah seniman visual yang lahir di Kupang, 21 November 1984[1] Karya-karya Armando berupa ilustras-ilustrasi dan komik. Armando belajar seni secara otodidak. Kegemarannya terhadap seni sudah ada semenjak SMA, kemudian Armandio ...

 

Ministry Woman and Child Development Government of Maharashtraमंत्रालय महिला व बालविकास विभाग महाराष्ट्र शासन Seal of the state of MaharashtraBuilding of Administrative Headquarters of MumbaiAgency overviewFormed1960; 63 years ago (1960)PrecedingDepartment of School EducationJurisdictionChief Minister of MaharashtraHeadquartersMantralaya, MumbaiAnnual budgetState budget of Government of Maharas...

 

Рінге Ringe —  громада  — Вид Рінге Координати: 52°35′ пн. ш. 6°56′ сх. д. / 52.583° пн. ш. 6.933° сх. д. / 52.583; 6.933 Країна  Німеччина Земля Нижня Саксонія Район Графство Бентгайм Об'єднання громад Емліхгайм Площа  - Повна 35,32 км² Ви

كابوتيرا     الإحداثيات 39°10′31″N 8°58′15″E / 39.1751871°N 8.9708519°E / 39.1751871; 8.9708519  [1] تقسيم إداري  البلد إيطاليا[2]  خصائص جغرافية  المساحة 68.49 كيلومتر مربع (9 أكتوبر 2011)[3]  ارتفاع 54 متر  عدد السكان  عدد السكان 23583 (1 يناير 2018)[4]  الكثافة...

 

البطولة الوطنية المغربية الموسم الحالي2022–2023 الجهة المنظمة الجامعة الملكية المغربية لكرة القدم  تاريخ الإنشاء 1956 الرياضة كرة القدم البلد المغرب القارة الكاف (أفريقيا) النسخة الأولى 1956–57 عدد الفرق 16 أحدث بطل الجيش الملكي(اللقب الـ13) الأكثر فوزا الوداد الرياضي (22 لقبًا) ...

 

Geographical features of Iceland Geography of IcelandContinentEuropeRegionNorthern EuropeCoordinates65°00′N 18°00′W / 65.000°N 18.000°W / 65.000; -18.000AreaRanked 106 • Total103,001 km2 (39,769 sq mi) • Land97.33% • Water2.67%Coastline4,970 km (3,090 mi)BordersNoneHighest pointHvannadalshnúkur2,110 m (6,920 ft)Lowest pointAtlantic Ocean0 m (0 ft)Longest riverÞjórsá230 km ...

artikel ini tidak memiliki pranala ke artikel lain. Tidak ada alasan yang diberikan. Bantu kami untuk mengembangkannya dengan memberikan pranala ke artikel lain secukupnya. (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 menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber:...

 

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article about school may require cleanup. Please review editing advice and help improve this article. (January 2022) 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: Cheltenham Secondary ...

 

2005 American filmKissing on the MouthDirected byJoe SwanbergWritten byKevin PittmanJoe SwanbergKris SwanbergKate WinterichProduced byJoe SwanbergStarringKevin PittmanJoe SwanbergKris SwanbergKate WinterichCinematographyJoe SwanbergEdited byJoe SwanbergDistributed byFilm1Release date March 12, 2005 (2005-03-12) Running time78 minutesCountryUnited StatesLanguageEnglish Kissing on the Mouth is a 2005 American film directed by Joe Swanberg.[1][2] The small cast ser...

Pan-Asian television channel Not to be confused with Food Network Asia. Television channel Asian Food NetworkCountrySingaporeBroadcast areaHong KongTaiwanMongoliaSoutheast AsiaHeadquarters21 Media Circle, #08-01, Infinite Studios, Singapore 138562ProgrammingPicture format1080i HDTV(downscaled to 16:9 480i/576i for the SDTV feed)OwnershipOwnerWarner Bros. Discovery Asia-PacificSister channelsCartoon NetworkWorld Heritage ChannelHBODiscovery ChannelTLCDMAXDiscovery ScienceEveDiscovery AsiaAnima...

 

Species of frog Leptodactylus rhodomystax Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Amphibia Order: Anura Family: Leptodactylidae Genus: Leptodactylus Species: L. rhodomystax Binomial name Leptodactylus rhodomystaxBoulenger, 1884[2] Synonyms Leptodactylus stictigularis Noble, 1923 Leptodactylus rhodomystax (common name: Loreto white-lipped frog, rose-lipped thin-toed frog) is ...

 

Election 1836 Boston mayoral election ← 1835 December 12, 1836 1837 →   Candidate Samuel Atkins Eliot John W. James Party Whig Democratic Popular vote 3,238 1,667 Percentage 56.98% 29.33% Mayor before election Samuel Turell Armstrong Whig Elected Mayor Samuel Atkins Eliot Whig Elections in Massachusetts General 1942 1944 1946 1948 1950 1952 1954 1956 1958 1960 1962 1964 1966 1970 1974 1978 1982 1986 1990 1994 1998 2002 2006 2008 2010 2012 2014 2016 2018 2020 20...

Carlos RodríguezInformacjeData i miejsce urodzenia2 lutego 2001AlmuñécarKrajHiszpaniaObecna grupaIneos GrenadiersWzrost183 cmGrupy zawodowe2020-8.2020Ineos9.2020-Ineos GrenadiersDokumentacja Carlos Rodríguez Cano (ur. 2 lutego 2001 w Almuñécar[1]) – hiszpański kolarz szosowy. Osiągnięcia Opracowano na podstawie:[1][2] 2018 1. miejsce w klasyfikacji młodzieżowej Tour de Gironde 1. miejsce w klasyfikacji punktowej 1. miejsce na 1. etapie 1. miejsce na etapie 2b Trophée Centre Morb...

 

British horologist, naval officer, author and radio personality (1890–1948) For the English theatre director, see Rupert Goold. Rupert GouldCommander R T GouldBornRupert Thomas Gould(1890-11-16)16 November 1890England, United Kingdom of Great Britain and IrelandDied5 October 1948(1948-10-05) (aged 57)Canterbury, Kent, England, United KingdomNationalityBritishOccupation(s)Author, radio personalitySpouseMuriel EstallChildrenCecil GouldJocelyne Stacey Rupert Thomas Gould (16 November 1890...

 

Method of removing a polyp with a sling In medicine, a polypectomy is the removal of an abnormal growth of tissue called a polyp. Polypectomy can be performed by excision if the polyp is external (on the skin).[1][additional citation(s) needed] See also Colonic polypectomy Non-lifting sign References ^ Li, Chao; Ellsmere, James (1 January 2019). Chapter 57 - Diagnostic and Therapeutic Endoscopy of the Stomach and Small Bowel. Shackelford's Surgery of the Alimentary Tract, 2 Vo...

1911 novella by André Gide Isabelle Second edition cover (1911)AuthorAndré GideTranslatorWalter BallenbergerLanguageFrenchGenreRécitSet inCalvados department, 1890sPublisherLes Éditions de la Nouvelle Revue FrançaisePublication date1911Pages194Dewey Decimal843.912 Isabelle is a novella (described as a récit) by André Gide, published in 1911.[1][2][3][4][5] Plot 25-year-old Gérard Lacase from the Sorbonne studies for his doctorate on Jacques...

 

2013 film by Kirk DeMicco and Chris Sanders This article is about the film. For the franchise, see The Croods (franchise). The CroodsTheatrical release posterDirected by Chris Sanders Kirk DeMicco Screenplay by Kirk DeMicco Chris Sanders Story by John Cleese[1] Kirk DeMicco Chris Sanders Produced by Kristine Belson Jane Hartwell Starring Nicolas Cage Emma Stone Ryan Reynolds Catherine Keener Cloris Leachman Clark Duke Edited by Eric Dapkewicz Darren T. Holmes Music byAlan Silvestri ...

 

Białe koszary Białe koszary (2023 r.) Państwo  Polska Miejscowość Stargard Adres ul. Aleja Żołnierza 37 Typ budynku koszary Kondygnacje 3 Rozpoczęcie budowy 1935 Ukończenie budowy 1938 Pierwszy właściciel Wojsko Niemieckie Kolejni właściciele Armia Czerwona/Radziecka Obecny właściciel Wojsko Polskie Położenie na mapie PolskiBiałe koszary 53°20′13,1125″N 15°00′46,9822″E/53,336976 15,013051 Multimedia w Wikimedia Commons Białe koszary, widok z 2009 r....

Division d’Honneur 1901-1902 Competizione Campionato belga di calcio Sport Calcio Edizione 7ª Organizzatore UBSSA Date dal 27 ottobre 1901al 4 maggio 1902 Luogo  Belgio Partecipanti 11 Risultati Vincitore Racing Club de Bruxelles(4º titolo) Statistiche Miglior marcatore Herbert Potts (16) Incontri disputati 63 Gol segnati 229 (3,63 per incontro) Cronologia della competizione 1900-1901 1902-1903 Manuale La Division d'Honneur 1901-1902 è stata la settima edizione del...

 

American film producer Not to be confused with Jason Blume. Jason BlumBlum at the 2018 San Diego Comic-ConBornJason Ferus Blum (1969-02-20) February 20, 1969 (age 54)[1]Los Angeles, California, U.S.Alma materVassar CollegeOccupation(s)Producer, studio executiveYears active1995–presentOrganizationBlumhouse ProductionsSpouse Lauren A.E. Schuker ​(m. 2012)​ParentShirley Neilsen Blum (mother) Jason Ferus Blum (/blʌm/;[2] born February...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!