Số n được cho l&agrave; số Carmichael nếu n&oacute; thỏa m&atilde;n điều kiện số học modulo sau:
<pre class="language-markup"><code>power(b, n-1) mod n = 1, 
với mọi b trong khoảng từ 1 tới n sao cho b v&agrave; n l&agrave; nguy&ecirc;n tố c&ugrave;ng nhau, hay, gcd(b, n) = 1</code></pre>
Cho một số nguy&ecirc;n dương n, b&agrave;i to&aacute;n x&aacute;c định xem n&oacute; c&oacute; phải l&agrave; một số Carmichael hay kh&ocirc;ng l&agrave; một b&agrave;i to&aacute;n c&oacute; &yacute; nghĩa quan trọng trong Phương ph&aacute;p kiểm tra nguy&ecirc;n tố x&aacute;c suất Fermat.
Chẳng hạn:
<pre class="language-markup"><code>Đầu v&agrave;o: n = 8
Đầu ra : false
Giải th&iacute;ch: 8 kh&ocirc;ng phải l&agrave; số Carmichael do 3 l&agrave; nguy&ecirc;n tố c&ugrave;ng nhau với 8 v&agrave; 3^{8-1} mod 8
 = 2187 % 8 kh&aacute;c 1.
 
Đầu v&agrave;o: n = 561
Đầu ra: true</code></pre>
&Yacute; tưởng rất đơn giản, ch&uacute;ng ta lặp qua tất cả c&aacute;c số từ 1 đến n v&agrave; với mọi số nguy&ecirc;n tố c&ugrave;ng nhau, ch&uacute;ng ta kiểm tra xem lũy thừa thứ (n-1) của n&oacute; theo modulo n c&oacute; l&agrave; 1 hay kh&ocirc;ng. Dưới đ&acirc;y l&agrave; một chương tr&igrave;nh để kiểm tra xem một số nhất định c&oacute; phải l&agrave; Carmichael hay kh&ocirc;ng.
<pre class="language-c"><code>#include &lt;stdio.h&gt;
int gcd(int a, int b)
{
 if (a &lt; b)
 return gcd(b, a);
 if (a % b == 0)
 return b;
 return gcd(b, a % b);
}


int power(int x, int y, int mod)
{
 if (y == 0)
 return 1;
 int temp = power(x, y / 2, mod) % mod;
 temp = (temp * temp) % mod;
 if (y % 2 == 1)
 temp = (temp * x) % mod;
 return temp;
}


bool isCarmichaelNumber(int n)
{
 for (int b = 2; b &lt; n; b++) {
 // Nếu "b" l&agrave; nguy&ecirc;n tố c&ugrave;ng nhau với n
 if (gcd(b, n) == 1)
 // V&agrave; pow(b, n-1)%n kh&aacute;c 1,
 // return false.
 if (power(b, n - 1, n) != 1)
 return false;
 }
 return true;
}


int main()
{
 printf(isCarmichaelNumber(500));
 printf(isCarmichaelNumber(561));
 printf(isCarmichaelNumber(1105));
 return 0;
}</code></pre>
Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; giải thuật về gi&aacute; trị số Carmichael, nếu c&aacute;c bạn c&oacute; bất kỳ thắc mắc n&agrave;o hoặc b&igrave;nh luận g&oacute;p &yacute;, c&aacute;c bạn c&oacute; thể gửi c&acirc;u hỏi l&ecirc;n tr&ecirc;n nh&oacute;m cộng của TEK4.VN nh&eacute;!
<hr />
Fanpage Facebook:&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a>&nbsp;
Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a>

Admin

Số Carmichael và thuật toán tìm số Carmichael

Cùng tác giả

Admin

Có liên quan