# For How Large an 'n' can the Carmichael Function of n be 2?

• patrickbotros
In summary, the largest possible value for n where λ(n)=2 is 24. This is because for p^2≡1 mod(n) to hold, n must be equal to 6a, where p is any number other than 2 and 3. Additionally, all p≤√n must also be included in n, so there must be a p# (the product of the first c primes) such that p_(c+1)>√p#. However, this does not hold for p>5.
patrickbotros
What is the largest n such that λ(n)=2? Is there such a bound? This isn't a homework question. I'm just interested.

If ##p## is not in ##n## than ##(p,n)=1 ##.
Therefore for ##p^2\equiv 1mod(n)## to hold ##n=6a## since all ##p## other than 2 and 3 are of the form ##6b\pm 1##
Also all ##p\leq \sqrt{n}## must be in ##n## since otherwise ##p^2<n##.
so we need a ##p\sharp## such that ##p_{c+1}>\sqrt{p\sharp}##.
It's easy to see that this does not hold for ##p>5##.
[EDIT:-##p\sharp=p_1\times p_2 \times p_3\times...\times p_c##.]

Did I scare you off ? I assumed you were familiar with some number theory terminology. If you have any questions, please ask.

## 1. What is the Carmichael Function of n?

The Carmichael Function of n, denoted as Φ(n), is a number-theoretic function that gives the smallest positive integer k such that a^k ≡ 1 (mod n) for all integers a that are relatively prime to n.

## 2. How is the Carmichael Function of n related to the Euler's Totient Function?

The value of Φ(n) is always less than or equal to φ(n), where φ(n) is the Euler's Totient Function. This is because the Carmichael Function considers both the prime and composite factors of n, while the Euler's Totient Function only considers the prime factors.

## 3. What is the significance of the number 2 in the question "For How Large an 'n' can the Carmichael Function of n be 2?"

The number 2 in the question represents the smallest possible value that the Carmichael Function can take. This is because a^1 ≡ 1 (mod n) for all integers a that are relatively prime to n, so the smallest possible value for k is 1. Therefore, we are trying to find the largest possible value for n, where Φ(n) = 1.

## 4. What is the largest known value for 'n' where the Carmichael Function of n is 2?

The largest known value for n where Φ(n) = 2 is 14,357,287, which was found by R. Pinch in 1975.

## 5. Is there a known formula for calculating the Carmichael Function of n?

There is no known formula for calculating the Carmichael Function of n. However, there are efficient algorithms for computing its value, such as the Pollard p-1 algorithm and the Elliptic Curve Method.

Replies
1
Views
981
Replies
1
Views
1K
Replies
1
Views
835
Replies
2
Views
2K
Replies
1
Views
945
Replies
6
Views
1K
Replies
4
Views
1K
Replies
12
Views
1K
Replies
2
Views
924
Replies
1
Views
1K