- #1

peteryellow

- 47

- 0

$(d+p)(p-1).$

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter peteryellow
- Start date

In summary, if $n=pqr$ is a Carmichael number and $q-1|pr-1$ and $r-1|pq-1$, it can be shown that $q-1$ is a divisor in $(d+p)(p-1)$, where $d$ is in the range of $[2, p-1]$. This is a well-known question and more research should be done before publishing such problems.

- #1

peteryellow

- 47

- 0

$(d+p)(p-1).$

Physics news on Phys.org

- #2

peteryellow

- 47

- 0

n=pqr is carmicahelnumber. if we have that r-1|pq-1 then I have shown that

pq-1=d(r-1) where d is [2;p-1]. Moreover I have shown that q-1|d(r-1)-p+1.

Now I want to show that if q-1|pr-1 is also fulfilled then q-1 is divisor in (d+p)(p-1). Do you understand it?

- #3

rscosa

- 14

- 1

I suggest you to read more before publish your problems since this is a very well known question (Wikipedia).

A Carmichael number is a composite number that satisfies the condition that $(d+p)(p-1)$ is a divisor of $q-1$ for all prime factors $p$ and their corresponding multiplicity $d$. In simpler terms, a Carmichael number is a number that passes the Fermat primality test for all possible bases.

Carmichael numbers are different from prime numbers because they are composite numbers, meaning they can be factored into smaller numbers. In contrast, prime numbers can only be divided evenly by 1 and themselves.

Carmichael numbers are useful in cryptography because they can act as potential "trapdoors" in encryption algorithms. This means that if someone tries to factor a large number that is a Carmichael number, they may mistakenly believe it is a prime number and their calculations will be incorrect.

Carmichael numbers are discovered using computer algorithms that test for the condition $(d+p)(p-1)$ being a divisor of $q-1$. They are verified by performing the Fermat primality test on each possible base and checking if the result is congruent to 1.

Yes, there are many known Carmichael numbers, with the smallest being 561. Some other examples include 1105, 1729, and 2465. It is estimated that there are infinitely many Carmichael numbers, but they become increasingly rare as the numbers get larger.

- Replies
- 1

- Views
- 1K

- Replies
- 8

- Views
- 1K

- Replies
- 11

- Views
- 1K

- Replies
- 1

- Views
- 2K

- Replies
- 2

- Views
- 1K

- Replies
- 3

- Views
- 1K

- Replies
- 19

- Views
- 2K

- Replies
- 4

- Views
- 1K

- Replies
- 11

- Views
- 1K

- Replies
- 4

- Views
- 2K

Share: