随机算法 (Spring 2013) and Carmichael number: Difference between pages
imported>Etone |
imported>Addbot |
||
Line 1: | Line 1: | ||
{{ | In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]]. | ||
< | |||
| | |||
All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. | |||
{{Math-stub}} | |||
[[Category:Number theory]] | |||
Latest revision as of 08:08, 11 March 2013
In number theory a Carmichael number is a composite positive integer [math]\displaystyle{ n }[/math], which satisfies the congruence [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ n }[/math]. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.
All prime numbers [math]\displaystyle{ p }[/math] satisfy [math]\displaystyle{ b^{p-1}\equiv 1\pmod{p} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ p }[/math]. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number [math]\displaystyle{ n }[/math] is composite, it does not satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. Template:Math-stub