We are creating the world's most trusted encyclopedia and knowledge base.
Once you join us and log in, you'll be able to edit this page instantly!

Carmichael number

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

Code ^[?]

This is a draft article, under development. These unapproved articles are subject to a disclaimer.

[edit intro]

A Carmichael number is a composite number named after the mathematician Robert Daniel Carmichael. A Carmichael number $\scriptstyle c\$ divides $\scriptstyle a^c - a\$ for every integer $\scriptstyle a\$ . A Carmichael number c also satisfies the congruence $\scriptstyle a^{c-1} \equiv 1 \pmod c$ , if $\scriptstyle \operatorname{gcd}(a,c) = 1$ . The first few Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601 and 8911. In 1994 Pomerance, Alford and Granville proved that there exist infinitely many Carmichael numbers.

Properties

Every Carmichael number is square-free and has at least three different prime factors
For every Carmichael number c it holds that $c - 1$ is divisible by $p n - 1$ for every one of its prime factors $p n$ .
Every Carmichael number is an Euler pseudoprime.
Every absolute Euler pseudoprime is a Carmichael number.

Chernick's Carmichael numbers

J. Chernick found in 1939 a way to construct Carmichael numbers^[1]. If, for a natural number n, the three numbers $\scriptstyle 6n+1\$ , $\scriptstyle 12n+1\$ and $\scriptstyle 18n+1\$ are prime numbers, the product $\scriptstyle M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)$ is a Carmichael number. Equivalent to this is that if $\scriptstyle m\$ , $\scriptstyle 2m-1\$ and $\scriptstyle 3m-2$ are prime numbers, then the product $\scriptstyle m\cdot (2m-1)\cdot (3m-2)$ is a Carmichael number.

To construct Carmichael numbers with $\scriptstyle M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)$ , you could only use numbers $n\$ which ends with 0, 1, 5 or 6.

This way to construct Carmichael numbers could expand to $M_k(n)=(6n+1)(12n+1)\prod_{i=1}^{k-2}(9\cdot 2^in+1)$ with the restriction, that for $(36\cdot 2^jm + 1)$ the variable $m\$ is divisible by $2^j\$