ฟังก์ชันคาร์ไมเคิล

Q: ข้อมูลสำคัญเกี่ยวกับ ฟังก์ชันคาร์ไมเคิล

ใน ทฤษฎีจำนวน ซึ่ง เป็นสาขาหนึ่งของ คณิตศาสตร์ ฟังก์ชัน คาร์ไมเคิล λ ( n ) ของ จำนวนเต็มบวก n คือจำนวนเต็มบวกที่เล็กที่สุด m ที่ทำให้

ในทฤษฎีจำนวน ซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์ฟังก์ชันคาร์ไมเคิล $λ$ $($ $n$ $)$ ของจำนวนเต็มบวก $n$ คือจำนวนเต็มบวกที่เล็กที่สุด $m$ ที่ทำให้

a^{m}\equiv 1{\pmod {n}}

เป็นจริงสำหรับจำนวนเต็มทุกตัว $ที่ เป็นจำนวนเฉพาะ$ สัมพัทธ์กับ $n$ ในทางพีชคณิต $λ$ $($ $n$ $)$ คือเลขชี้กำลังของกลุ่มการคูณของจำนวนเต็มมอดู $ล n$ เนื่องจากนี่เป็นกลุ่มอาเบเลียนจำกัดจึงต้องมีสมาชิกที่มีอันดับเท่ากับเลขชี้กำลัง $λ$ $($ $n$ $)$ สมาชิกดังกล่าวเรียกว่า ราก $λ$ ดั้งเดิมมอดู $ล$ n

$ฟังก์ชัน λ$ ของ Carmichael : $λ$ $($ $n$ $)$ สำหรับ $1 \leq$ $n$ $\leq 1000$ (เปรียบเทียบกับ ฟังก์ชัน $φ$ ของ Euler )

ฟังก์ชันคาร์ไมเคิลตั้งชื่อตามโรเบิร์ต คาร์ไมเคิล นักคณิตศาสตร์ชาวอเมริกัน ผู้กำหนดนิยามฟังก์ชันนี้ในปี พ.ศ. 2453 ^{[ 1 ]}นอกจากนี้ยังรู้จักกันในชื่อฟังก์ชัน λ ของคาร์ไมเคิลฟังก์ชันโทเทียนต์แบบลดรูปและฟังก์ชันเลขชี้กำลัง สากลที่น้อยที่สุด

อันดับของกลุ่มการคูณของจำนวนเต็มมอดู $ล n$ คือ $φ$ $($ $n$ $)$ โดยที่ $φ$ คือฟังก์ชันโทเทียนต์ของออยเลอร์เนื่องจากอันดับของสมาชิกในกลุ่มจำกัดหารอันดับของกลุ่มลงตัว ดังนั้น $λ$ $($ $n$ $)$ จึงหาร $φ$ $($ $n$ $)$ ลงตัว ตารางต่อไปนี้เปรียบเทียบค่า $λ$ $($ $n$ $)$ 36 ค่าแรก (ลำดับA002322ในOEIS ) และ $φ$ $($ $n$ $)$ ( ตัวหนาหากค่าทั้งสองแตกต่างกัน ค่า $n$ ที่ทำให้ค่าทั้งสองแตกต่างกันแสดงอยู่ใน (ลำดับA033949ในOEIS ))

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
$λ (n)$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12	18	6	28	4	30	8	10	16	12	6
$φ (n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12

ตัวอย่างเชิงตัวเลข

$n = 5$ เซตของจำนวนที่น้อยกว่าและเป็นจำนวนเฉพาะสัมพัทธ์กับ 5 คือ ${1,2,3,4$ } ดังนั้นฟังก์ชันโทเทียนต์ของออยเลอร์มีค่า $φ$ $(5) = 4$ และค่าของฟังก์ชันของคาร์ไมเคิล $λ$ $(5)$ ต้องเป็นตัวหารของ 4 ตัวหาร 1 ไม่ตรงตามนิยามของฟังก์ชันของคาร์ไมเคิลยกเว้น และ2 ก็ไม่ตรงตามนิยามเช่นกันเนื่องจาก ดังนั้น $λ$ $(5) = 4$ อันที่จริง $ทั้ง 2 และ 3 เป็นราก λ$ ดั้งเดิมมอดูล 5 และ เป็น รากดั้งเดิมมอดูล 5 $a^{1}\not \equiv 1{\pmod {5}}$ $a\equiv 1{\pmod {5}}$ $2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}$ $1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}$
$n = 8$ เซตของจำนวนที่น้อยกว่าและเป็นจำนวนเฉพาะสัมพัทธ์กับ 8 คือ ${1,3,5,7}$ ดังนั้น $φ$ $(8) = 4$ และ $λ$ $(8)$ ต้องเป็นตัวหารของ 4 ในความเป็นจริง $λ$ $(8) = 2$ เนื่องจาก $ราก λ$ ดั้งเดิมมอดูล 8 คือ 3, 5 และ 7 ไม่มีรากดั้งเดิมมอดูล 8 $1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}$

ความสัมพันธ์เวียนเกิดสำหรับ $λ$ $($ $n$ $)$

ฟังก์ชันแลมบ์ดาของคาร์ไมเคิลของกำลังเฉพาะสามารถแสดงได้ในรูปของโทเทียนต์ของออยเลอร์ จำนวนใดๆ ที่ไม่ใช่ 1 หรือกำลังเฉพาะ สามารถเขียนได้อย่างไม่ซ้ำกันในรูปผลคูณของกำลังเฉพาะที่แตกต่างกัน โดยที่ $λ$ ของผลคูณจะเป็นตัวคูณร่วมน้อยที่สุดของ $λ$ ของตัวประกอบกำลังเฉพาะ โดยเฉพาะอย่างยิ่ง $λ$ $($ $n$ $)$ กำหนดโดยความสัมพันธ์เวียนเกิดดังนี้

\lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odd prime power,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are powers of distinct primes.}}\end{cases}}

ค่าโทเทียนต์ของออยเลอร์สำหรับกำลังของจำนวนเฉพาะ นั่นคือ จำนวน $p$ $r$ โดยที่ $p$ เป็น จำนวนเฉพาะและ $r$ $\geq 1$ กำหนดโดย

\varphi (p^{r}){=}p^{r-1}(p-1).

ทฤษฎีบทของคาร์ไมเคิล

คาร์ไมเคิลพิสูจน์ทฤษฎีบทสองข้อที่เมื่อรวมกันแล้วจะแสดงให้เห็นว่า หาก พิจารณา $λ$ $($ $n$ $)$ ตามที่กำหนดไว้โดยความสัมพันธ์เวียนเกิดในส่วนก่อนหน้าแล้ว λ(n) จะสอดคล้องกับคุณสมบัติที่ระบุไว้ในบทนำ กล่าวคือ λ(n) เป็นจำนวนเต็มบวกที่เล็กที่สุดm $ซึ่ง$ สำหรับทุก $a ที่$ เป็นจำนวนเฉพาะสัมพัทธ์กับ $n$ $a^{m}\equiv 1{\pmod {n}}$

ทฤษฎีบท 1 —ถ้า $a$ เป็นจำนวนเฉพาะสัมพัทธ์กับ $n$ แล้ว. ^[²^] $a^{\lambda (n)}\equiv 1{\pmod {n}}$

สิ่งนี้หมายความว่าลำดับขององค์ประกอบทุกตัวของกลุ่มการคูณของจำนวนเต็มมอดู ล $n หาร$ $λ$ $($ $n$ $)$ ลงตัวคาร์ไมเคิลเรียกองค์ประกอบ $a$ ซึ่งเป็นกำลังน้อยที่สุดของ $a$ ที่สอดคล้องกับ 1 (mod $n$ ) ว่าราก λ ดั้งเดิมมอดูล n [ ³^]⁽สิ่งนี้ไม่ควรสับสนกับรากดั้งเดิมมอดูล $n$ ซึ่งคาร์ไมเคิลบางครั้งเรียกว่ารากดั้งเดิมมอดู $ล n$ ) $a^{\lambda (n)}$ $\varphi$

ทฤษฎีบท 2 —สำหรับจำนวนเต็มบวก $n ทุกตัว จะมีราก$ $λ$ ดั้งเดิม มอดู $ล n$ อยู่นอกจากนี้ ถ้า $g$ เป็นรากดังกล่าว ก็จะมี^ราก $λ$ ดั้งเดิมที่สอดคล้องกับกำลังของ $g$ [ ⁴^] $\varphi (\lambda (n))$

ถ้า $g เป็นหนึ่งในราก$ $λ$ ดั้งเดิมที่รับประกันโดยทฤษฎีบท แสดงว่าไม่มีคำตอบจำนวนเต็มบวก $m$ ที่น้อยกว่า $λ$ $($ $n$ $)$ ซึ่งแสดงว่าไม่มี $m$ $<$ $λ$ $($ $n$ $)$ ที่เป็นบวกใดๆ ที่ทำให้สำหรับทุก $a$ ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ $n$ $g^{m}\equiv 1{\pmod {n}}$ $a^{m}\equiv 1{\pmod {n}}$

ข้อความที่สองของทฤษฎีบท 2 ไม่ได้หมายความว่า ราก $λ$ ดั้งเดิมทั้งหมด มอดู $ล n$ จะสอดคล้องกับกำลังของราก $g$ เพียงราก เดียว^{[ 5 ]}ตัวอย่างเช่น ถ้า $n$ $= 15$ แล้ว $λ$ $($ $n$ $) = 4$ ในขณะที่และมีราก $λ$ ดั้งเดิมสี่ รากมอดูล 15 ได้แก่ 2, 7, 8 และ 13 เนื่องจากราก 2 และ 8 สอดคล้องกับกำลังของกันและกัน และราก 7 และ 13 สอดคล้องกับกำลังของกันและกัน แต่ทั้ง 7 และ 13 ไม่สอดคล้องกับกำลังของ 2 หรือ 8 และในทางกลับกัน องค์ประกอบอีกสี่ตัวของกลุ่มการคูณมอดูล 15 ได้แก่ 1, 4 (ซึ่งสอดคล้องกับ), 11 และ 14 ไม่ใช่ราก $λ$ ดั้งเดิม มอดูล 15 $\varphi (n)=8$ $\varphi (\lambda (n))=2$ $1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}$ $4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}$

เพื่อเป็นตัวอย่างเปรียบเทียบ ถ้า $n$ $= 9$ แล้วและ มีราก $λ$ ดั้งเดิมสองตัวมอดูล 9 คือ 2 และ 5 ซึ่งแต่ละตัวสมมูลกับกำลังห้าของอีกตัวหนึ่ง นอกจากนี้ทั้งสองยังเป็นราก λ ดั้งเดิมมอดูล 9 ด้วย $\lambda (n)=\varphi (n)=6$ $\varphi (\lambda (n))=2$ $\varphi$

คุณสมบัติของฟังก์ชันคาร์ไมเคิล

ในส่วนนี้จำนวนเต็ม จะหารลงตัวด้วยจำนวนเต็มที่ไม่เป็นศูนย์ก็ต่อเมื่อมีจำนวนเต็มอยู่จริงที่ทำให้ซึ่งเขียนได้ดังนี้ $n$ $m$ $k$ $n=km$

m\mid n.

ผลที่ตามมาจากการมีค่าต่ำสุดของ $λ$ $($ $n$ $)$

สมมติว่า $m$ $\equiv 1 (mod$ $n$ $)$ สำหรับจำนวน a ที่เป็นจำนวนเฉพาะ $สัมพัทธ์$ $กับ$ n $แล้ว$ λ $($ $n$ $)$ $|$ $m$ .

บทพิสูจน์:ถ้า $m$ $=$ $kλ$ $($ $n$ $) +$ $r$ โดยที่ $0 \leq$ $r$ $<$ $λ$ $($ $n$ $)$ แล้ว

a^{r}=1^{k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}=a^{k\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}

สำหรับจำนวนทั้งหมด $a$ ที่เป็นจำนวน เฉพาะสัมพัทธ์กับ $n$ ดังนั้นจึงสรุปได้ว่า $r = 0$ เนื่องจาก $r$ $<$ $λ$ $($ $n$ $)$ และ $λ$ $($ $n$ $)$ คือเลขชี้กำลังบวกขั้นต่ำสุดที่ทำให้ความสอดคล้องเป็นจริงสำหรับจำนวนทั้งหมด $a$ ที่เป็น จำนวน เฉพาะสัมพัทธ์กับ $n$

$λ (n) หาร$ $φ$ $($ $n$ $)$ ลงตัว

สิ่งนี้เป็นผลมาจาก ทฤษฎีกลุ่มเบื้องต้นเนื่องจากเลขชี้กำลังของกลุ่มจำกัด ใดๆ จะต้องหารลงตัวกับอันดับของกลุ่มนั้น $λ$ $($ $n$ $)$ คือเลขชี้กำลังของกลุ่มการคูณของจำนวนเต็มมอดู $ล n$ ในขณะที่ $φ$ $($ $n$ $)$ คืออันดับของกลุ่มนั้น โดยเฉพาะอย่างยิ่ง ทั้งสองจะต้องเท่ากันในกรณีที่กลุ่มการคูณเป็นกลุ่มวัฏจักรเนื่องจากการมีอยู่ของรากปฐมภูมิซึ่งเป็นกรณีสำหรับกำลังของจำนวนเฉพาะคี่

ดังนั้น เราจึงสามารถมองทฤษฎีบทของคาร์ไมเคิลว่าเป็นการพัฒนาต่อยอดจากทฤษฎีบทของออยเลอร์ได้

การหารลงตัว

a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)

การพิสูจน์.

ตามนิยาม สำหรับจำนวนเต็มใดๆที่มี(และด้วยเหตุนี้ด้วย) เราจะได้ว่าและดังนั้นสิ่งนี้พิสูจน์ได้ว่าสำหรับทุก $k$ ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ $a$ โดยผลสืบเนื่องของความน้อยที่สุดที่พิสูจน์ไว้ข้างต้น เราจะได้ว่า $k$ $\gcd(k,b)=1$ $\gcd(k,a)=1$ $b\,|\,(k^{\lambda (b)}-1)$ $a\,|\,(k^{\lambda (b)}-1)$ $k^{\lambda (b)}\equiv 1{\pmod {a}}$ $\lambda (a)\,|\,\lambda (b)$

องค์ประกอบ

$สำหรับจำนวนเต็มบวก a$ และ $b$ ทุกตัวจะเป็นจริงว่า

\lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))

.

นี่เป็นผลสืบเนื่องโดยตรงจากการเกิดซ้ำของฟังก์ชันคาร์ไมเคิล

ความยาวรอบเลขชี้กำลัง

ถ้าเป็นเลขชี้กำลังที่ใหญ่ที่สุดในการแยกตัวประกอบเฉพาะของ $n$ แล้ว สำหรับทุก $a$ (รวมถึง a ที่ ไม่เป็นจำนวนเฉพาะสัมพัทธ์กับ $n$ ) และทุก $r$ $\geq$ $r$ $max$ $r_{\mathrm {max} }=\max _{i}\{r_{i}\}$ $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$

a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.

โดยเฉพาะอย่างยิ่ง สำหรับ $n$ ที่ไม่มีตัวประกอบกำลังสอง ( $r$ $max$ $= 1$ ) สำหรับทุกค่า $a$ เราจะได้ว่า

a\equiv a^{\lambda (n)+1}{\pmod {n}}.

ค่าเฉลี่ย

สำหรับ $n$ $\geq 16$ ใดๆ : ^[⁶^]^[⁷^]

{\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ln \ln \ln n)}

(ต่อไปนี้เรียกว่าการประมาณของ Erdős) โดยมีค่าคงที่

B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537

และ $γ$ $\approx 0.57721$ ซึ่งเป็นค่าคงที่ของออยเลอร์-มาสเชโรนี

$ตารางต่อไปนี้แสดงภาพรวมของ 2$ $26$ $- 1 =$ แรก $67,108,863$ ค่าของ $ฟังก์ชัน λ$ สำหรับทั้งค่าเฉลี่ยที่แม่นยำและการประมาณค่า $แบบ$ $Erdős$

นอกจากนี้ ยังมีภาพรวมของค่า “ลอการิทึมทับลอการิทึม” ที่เข้าถึงได้ง่ายกว่า $LoL(n) := ⁠ ln λ (n) / ln n ด้วย$

$LoL(n) > ⁠ 4 / 5 ⁠ \Leftrightarrow λ (n) > n ⁠ 4 / 5 ⁠$ .

ตรงนั้นคือข้อมูลในตาราง แถวที่ 26 คอลัมน์

$% โลล > ⁠ 4 / 5 \to$ 60.49

แสดงว่า 60.49% (≈40,000,000 $)$ ของจำนวนเต็ม1 $\leq$ $n$ ≤ $67108863$ มี $λ$ $($ $n$ $) >$ $n$ $⁠$ $4 / 5 หมายความ$ $ว่าค่า λ$ ส่วนใหญ่เป็นแบบเลขชี้กำลังตามความยาว $l$ $:= log$ $2$ $($ $n$ $)$ ของอินพุต $n$ กล่าวคือ

\left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right)^{\frac {4}{5}}=n^{\frac {4}{5}}.

$ν$	$n = 2 ν - 1$	ผลรวม $\sum _{i\leq n}\lambda (i)$	เฉลี่ย ${\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)$	ค่าเฉลี่ยของ Erdős	เออร์โดส / ค่าเฉลี่ยที่แน่นอน	ค่าเฉลี่ย $LoL$	% $โลล$ > ⁠4/5⁠	% $โลล$ > ⁠7/8⁠
5	31	270	8.709677	68.643	7.8813	0.678244	41.94	35.48
6	63	964	15.301587	61.414	4.0136	0.699891	38.10	30.16
7	127	3574	28.141732	86.605	3.0774	0.717291	38.58	27.56
8	255	12994	50.956863	138.190	2.7119	0.730331	38.82	23.53
9	511	48032	93.996086	233.149	2.4804	0.740498	40.90	25.05
10	1023	178816	174.795699	406.145	2.3235	0.748482	41.45	26.98
11	2047	662952	323.865169	722.526	2.2309	0.754886	42.84	27.70
12	4095	2490948	608.290110	1304.810	2.1450	0.761027	43.74	28.11
13	8191	9382764	1145.496765	2383.263	2.0806	0.766571	44.33	28.60
14	16383	35504586	2167.160227	4392.129	2.0267	0.771695	46.10	29.52
15	32767	134736824	4111.967040	8153.054	1.9828	0.776437	47.21	29.15
16	65535	513758796	7839.456718	15225.43	1.9422	0.781064	49.13	28.17
17	131071	1964413592	14987.40066	28576.97	1.9067	0.785401	50.43	29.55
18	262143	7529218208	28721.79768	53869.76	1.8756	0.789561	51.17	30.67
19	524287	28935644342	55190.46694	101930.9	1.8469	0.793536	52.62	31.45
20	1048575	111393101150	106232.8409	193507.1	1.8215	0.797351	53.74	31.83
21	2097151	429685077652	204889.9090	368427.6	1.7982	0.801018	54.97	32.18
22	4194303	1660388309120	395867.5158	703289.4	1.7766	0.804543	56.24	33.65
23	8388607	6425917227352	766029.1187	1345633	1.7566	0.807936	57.19	34.32
24	16777215	24906872655990	1484565.386	2580070	1.7379	0.811204	58.49	34.43
25	33554431	96666595865430	2880889.140	4956372	1.7204	0.814351	59.52	35.76
26	67108863	375619048086576	5597160.066	9537863	1.7041	0.817384	60.49	36.73

ช่วงเวลาปัจจุบัน

สำหรับจำนวน $N$ ทั้งหมด และจำนวนเต็มบวก $n$ $\leq$ $N ทั้งหมด ยกเว้น$ $o$ $($ $N$ $)$ ^[⁸^] (เสียงข้างมากที่ "แพร่หลาย"):

\lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}

โดยมีค่าคงที่^{[ 7 ]}

A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688

ขอบเขตล่าง

$สำหรับจำนวน N$ ที่มีขนาดใหญ่เพียงพอและสำหรับ $Δ \geq (ln ln N) 3$ ใดๆ จะมีอย่างมากที่สุด

N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)

จำนวนเต็มบวก $n$ $\leq N$ โดยที่ $λ$ $($ $n$ $) \leq$ $ne$ $-Δ$ . ^[⁹^]

สั่งซื้อขั้นต่ำ

สำหรับลำดับจำนวนเต็มบวก ใดๆ $n$ $1$ $<$ $n$ $2$ $<$ $n$ $3$ $< \dots ค่าคงที่ใดๆ$ $0 <$ $c$ $<$ $⁠$ $1 / ln 2$ และ $i$ $ที่$ มีขนาดใหญ่เพียงพอใดๆ :^{[ 10 ]}^{[ 11 ]}

\lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.

ค่าเล็กน้อย

สำหรับค่าคงที่ $c$ และค่าบวก $A$ ที่มีขนาดใหญ่เพียงพอ จะมีจำนวนเต็ม $n$ $>$ $A$ อยู่ เช่นนั้น^[¹¹^]

\lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.

นอกจากนี้ $n$ ยังมีรูปแบบดังนี้

n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q

สำหรับจำนวนเต็มที่ไม่มีกำลังสอง $m$ $< (ln$ $A$ $)$ $c$ $ln ln ln$ $A$ . ^[¹⁰^]

ภาพของฟังก์ชัน

ชุดค่าของฟังก์ชันคาร์ไมเคิลมีฟังก์ชันการนับ^{[ 12 ]}

{\frac {x}{(\ln x)^{\eta +o(1)}}},

ที่ไหน

\eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607

ใช้ในวิทยาการเข้ารหัสลับ

ฟังก์ชันคาร์ไมเคิลมีความสำคัญในด้านการเข้ารหัสลับเนื่องจากถูกนำไปใช้ในอั ลกอริธึมการเข้ารหัส RSA

การพิสูจน์ทฤษฎีบทที่ 1

สำหรับ $n$ $=$ $p$ ซึ่งเป็นจำนวนเฉพาะ ทฤษฎีบทที่ 1 เทียบเท่ากับทฤษฎีบทเล็กของแฟร์มาต์ :

a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.

สำหรับกำลังของจำนวนเฉพาะ $p$ $r$ , $r$ $> 1$ ถ้า

a^{p^{r-1}(p-1)}=1+hp^{r}

เป็นจริงสำหรับจำนวนเต็ม $h$ บางค่า จากนั้นยกกำลัง $p$ ทั้งสองข้าง จะได้

a^{p^{r}(p-1)}=1+h'p^{r+1}

สำหรับจำนวนเต็มอื่น ๆ บางจำนวนโดยวิธีการอุปนัย จะได้ว่าสำหรับทุก ๆ $จำนวน$ เฉพาะสัมพัทธ์กับ $p$ และด้วยเหตุนี้กับ $p$ $r$ ซึ่งเป็นการพิสูจน์ทฤษฎีบทสำหรับ $n$ $= 4$ หรือกำลังของจำนวนเฉพาะคี่ใด ๆ $h'$ $a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}$

การปรับปรุงผลลัพธ์สำหรับเลขยกกำลังสองที่สูงขึ้น

สำหรับ $จำนวน$ เฉพาะสัมพัทธ์กับ (กำลังของ) 2 เราจะได้a $=$ $1 + 2h²$ $สำหรับ$ จำนวนเต็ม $h² บาง$ $ตัว$ $ดังนั้น$

a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}

,

โดยที่เป็นจำนวนเต็ม เมื่อ $r$ $= 3$ จะเขียนได้ดังนี้ $h_{3}$

a^{2^{r-2}}=1+2^{r}h_{r}.

ยกกำลังสองทั้งสองข้างจะได้

a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},

โดยที่เป็นจำนวนเต็ม จึงสรุปได้โดยการอุปมานว่า $h_{r+1}$

a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}

สำหรับทั้งหมดและทั้งหมด $เป็น$ จำนวนเฉพาะสัมพัทธ์กับ. ^[¹³^] $r\geq 3$ $2^{r}$

จำนวนเต็มที่มีตัวประกอบเฉพาะหลายตัว

ตามทฤษฎีบทการแยกตัวประกอบที่ไม่ซ้ำกัน $n$ $> 1$ ใดๆสามารถเขียนได้ในรูปแบบที่ไม่ซ้ำกันดังนี้

n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}

โดยที่ $p$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $k$ เป็นจำนวนเฉพาะ และ $r$ $1$ $,$ $r$ $2$ $, ...,$ $r$ $k$ เป็นจำนวนเต็มบวก ผลลัพธ์สำหรับกำลังของจำนวนเฉพาะแสดงให้เห็นว่า สำหรับ, $1\leq j\leq k$

a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.

จากสิ่งนี้จึงสรุปได้ว่า

a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,

โดยที่ ตามที่ระบุไว้ในความสัมพันธ์เวียนเกิด

\lambda (n)=\operatorname {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.

จากทฤษฎีบทเศษเหลือของจีนสรุปได้ว่า

a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.

ดูเพิ่มเติม

หมายเลขคาร์ไมเคิล

หมายเหตุ

^ Carmichael, Robert Daniel (1910). "หมายเหตุเกี่ยวกับฟังก์ชันทฤษฎีจำนวนใหม่" . Bulletin of the American Mathematical Society . 16 (5): 232– 238. doi : 10.1090/S0002-9904-1910-01892-9 .
^คาร์ไมเคิล (1914) หน้า 40
^คาร์ไมเคิล (1914) หน้า 54
^คาร์ไมเคิล (1914) หน้า 55
^คาร์ไมเคิล (1914) หน้า 56
^ทฤษฎีบทที่ 3 ใน Erdős (1991)
อรรถ เป็น^ข ^ซานดอร์ แอนด์ เครสติซี (2004) หน้า 194
↑ทฤษฎีบท 2 ใน Erdős (1991) 3. ลำดับปกติ (หน้า 365)
^ทฤษฎีบทที่ 5 ใน Friedlander (2001)
อรรถ^ข ^{ทฤษฎีบท} 1 ใน Erdős (1991)
อรรถ เป็น^ข ^ซานดอร์ แอนด์ เครสติซี (2004) หน้า 193
^ Ford, Kevin; Luca, Florian; Pomerance, Carl (27 สิงหาคม 2014). "ภาพของ ฟังก์ชัน λ ของ Carmichael ". พีชคณิตและทฤษฎีจำนวน 8 ( 8): 2009– 2026. arXiv : 1408.6506 . doi : 10.2140/ant.2014.8.2009 . S2CID 50397623 .
^คาร์ไมเคิล (1914) หน้า 38–39

[1] Carmichael, Robert Daniel (1910). "หมายเหตุเกี่ยวกับฟังก์ชันทฤษฎีจำนวนใหม่" . Bulletin of the American Mathematical Society . 16 (5): 232– 238. doi : 10.1090/S0002-9904-1910-01892-9 .

[2] คาร์ไมเคิล (1914) หน้า 40

[3] คาร์ไมเคิล (1914) หน้า 54

[4] คาร์ไมเคิล (1914) หน้า 55

[5] คาร์ไมเคิล (1914) หน้า 56

[6] ทฤษฎีบทที่ 3 ใน Erdős (1991)

[HBII194-7] อรรถ เป็น^ข ^ซานดอร์ แอนด์ เครสติซี (2004) หน้า 194

[8] ทฤษฎีบท 2 ใน Erdős (1991) 3. ลำดับปกติ (หน้า 365)

[9] ทฤษฎีบทที่ 5 ใน Friedlander (2001)

[Theorem_1_in_Erdős_(1991)-10] อรรถ^ข ^{ทฤษฎีบท} 1 ใน Erdős (1991)

[HBII193-11] อรรถ เป็น^ข ^ซานดอร์ แอนด์ เครสติซี (2004) หน้า 193

[12] Ford, Kevin; Luca, Florian; Pomerance, Carl (27 สิงหาคม 2014). "ภาพของ ฟังก์ชัน λ ของ Carmichael ". พีชคณิตและทฤษฎีจำนวน 8 ( 8): 2009– 2026. arXiv : 1408.6506 . doi : 10.2140/ant.2014.8.2009 . S2CID 50397623 .

[13] คาร์ไมเคิล (1914) หน้า 38–39

[ 1 ]

[

3

ราก

[ 5 ]

[

[

[

[

[ 10 ]

[ 11 ]

[ 12 ]

[