Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [carmichael-numbers]

Use this tag for questions about composite numbers n that satisfy b^(n-1) ≡ 1 (mod n) for all integers b relatively prime to n.

1
vote
1answer
31 views

Miller’s test for the base $b$

Definition: Let $n$ be an integer with $n > 2$ and $n − 1 = 2^st$, where $s$ is a non-negative integer and $t$ is an odd positive integer. We say that $n$ passes Miller’s test for the base $b$ if ...
2
votes
1answer
46 views

Large Carmichael number

I need to find or generate a very large Carmichael number (500 digits or longer). I've tried to find a database or just an example of such a number but failed. Is there any examples of really big ...
0
votes
1answer
60 views

Fermat's Little Theorem and Carmichael Numbers

Fermat's little theorem states that if $p$ is a prime number and $a$ is a positive integer, then $p|a^p-a$. However, the converse is false, that is, for integers $a$ and $p$, if $p|a^p-a$, then $a$ ...
1
vote
1answer
26 views

Carmicheal numbers are square free

Carmichael number square free I was reading this question.can some one explain how to arrive from here In particular, $a^{n−1} \equiv 1\pmod{p^t}$, to here $a^n \equiv a\pmod{p^2}$. Thank you
1
vote
0answers
42 views

Can a finite set of bases guarantee that a number is Carmichael or prime?

If a positive integer $N>1$ is a Carmichael number, it passes the weak Fermat-pseudoprime-test for every base coprime to it. I wonder whether the converse is true in the following sense : Is ...
2
votes
1answer
52 views

Reducing modulo $15841$

I want reduce the following congruence $17^{15842}\pmod{15841}$. My first stab at this was to use Fermat's Little Theorem, but then I realized that $15841$ is not a prime number. In fact, $$15841 ...
3
votes
1answer
105 views

Every integer in the form $(6m + 1)(12m + 1)(18m + 1)$, is a carmichael number.

Question: Show that every integer of the form $(6m + 1)(12m + 1)(18m + 1)$, where m is a positive integer such that $6m + 1$, $12m + 1$, and $18m + 1$ are all primes, is a Carmichael Number I know ...
1
vote
0answers
19 views

Infinitude of Carmichael numbers congruent to $a \pmod d$

Show that if $a$ and $d$ are relatively prime, then there are infinitely many Carmichael Numbers to $a \pmod d$. (i.e. composite numbers satisfying Fermat's Little theorem, $a^{n-1} = 1 \pmod n$ if $...
1
vote
0answers
89 views

Carmichael Numbers and generators

Suppose $n$ is a Carmichael number. If, for a contradiction, we supposed that $n=p^k m$ for a prime $p$ and some $k\ge 2$ where $gcd(m,p)=1$. Let $g$ be a generator mod $p^2$. I am looking to ...
6
votes
1answer
59 views

Asymmetry for Carmichael 'twins'

Using a table of Carmichael numbers up to $10^{16}$, there are $34971$ pairs $(c-2,c)$ where $c$ is a Carmichael number and $c-2$ is prime but only $204$ pairs $(c,c+2)$ with $c+2$ prime. Is there ...