互素

✍ dations ◷ 2025-05-04 12:46:43 #数论

互质(英文:coprime,符号:⊥,又称互素、relatively prime、mutually prime、co-prime)。在数论中,如果两个或两个以上的整数的最大公约数是 1,则称它们为互质。依此定义:

两个整数 ab 互素,记为 ab

例如 810 的最大公约数是 2,不是 1,因此它们并不互质。
又例如 7, 10, 13 的最大公约数是 1,因此它们互质。

最大公因数可以通过辗转相除法得到。

三个或三个以上的整数互质有两种不同的情况:

两两互素是较为严格的互素,如果一个整数集合是两两互素的,它也必定是整集互素,但是整集互素不必然是两两互素,甚至可能两两皆不互素,例如 gcd ( 6 , 15 , 10 ) = 1 {\displaystyle \gcd(6,15,10)=1} ,是整集互素,但 gcd ( 6 , 15 ) = 3 {\displaystyle \gcd(6,15)=3} gcd ( 15 , 10 ) = 5 {\displaystyle \gcd(15,10)=5} gcd ( 10 , 6 ) = 2 {\displaystyle \gcd(10,6)=2} ,任两者皆不互素。

性质之一:整数a和b互质当且仅当存在整数x,y使得xa+yb=1。 或者,一般的,有存在整数x,y使得xa+yb=d,其中d是a和b的最大公因数。(贝祖等式)

相关

  • 福赫伯福赫伯(英语:Herbert Franke,又译傅海波或杨瑀;1914年9月17日–2011年6月10日)是一位德国汉学家。他以研究金朝和元朝历史而闻名。他同时为《剑桥中国辽西夏金元史》的主编之一。
  • 三乙胺三乙胺(分子式:N(CH2CH3)3)是一种胺类有机化合物。三乙胺是无色至淡黄色的透明液体,有刺激的腥味,味道极苦,在空气中微发烟。微溶于水,能溶于乙醇、乙醚。水溶液呈碱性。易燃,其蒸气
  • 托管网页托管服务(英语:web hosting service)利用数据中心的电脑群和贮存设备为用户提供免费或收费服务。托管公司通常会提供一个界面,让用户远程上传网页内容,然后其他人就可以透过
  • 介子原子K介子原子是一种由K介子和质子构成的奇异原子,是在高能加速器研究机构中的 X-射线光谱发现他。K介子原子的半衰期有 1.18 ×10-18秒。
  • 中屯岛中屯岛又名中屯屿,是一个在台湾西南方的小岛,隶属于澎湖县白沙乡,周长5.1819公里。该岛是澎湖列岛中的第十一大岛,位于澎湖岛和白沙岛之间,形似土墩,因而旧名中墩。台湾日治时期,设
  • 1943年钢制1美分硬币1943年钢制1美分硬币(英语:steelie),是在二战期间因为铜的短缺而发行的一种钢制硬币。此种硬币由费城铸币局,丹佛铸币局和旧金山铸币局铸造。有别于成分为青铜的一般硬币,此种硬币
  • 天象天文现象是天体到了某个特定位置(客观上的位置)或状态而造成的特殊现象。有些天文现象是占星术上的热门话题,事实上观测天文现象是研究和拍摄天体的好机会,例如小行星掩星的联合
  • 马克斯·施泰纳马克斯·施泰纳(英语:Max Steiner,1888年5月10日-1971年12月28日),奥地利-美国电影配乐作曲家,影片《金刚》 (1933)、《飘》(1939)、《卡萨布兰卡》(1942)、《A Summer Place》(195
  • MediaGXMediaGX是Cyrix公司于1997年所发创、开展的x86整合型处理器,该处理器虽由Cyrix公司所设计,但Cyrix公司为Fabless型态的半导体业者,没有自属的晶圆厂,因此发表之初是委托IBM公司
  • 银行家算法银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为