# This appears to be in direct violation of Carmichael's theorem.

• Whovian
In summary, the conversation discusses an attempt to prove a statement about residues of a certain sequence mod ##10^n##. The individual has derived something that seems to go against Carmichael's theorem, and is seeking clarification on where their reasoning may be incorrect. They point out that according to Euler's theorem, certain congruences hold by induction, and then go on to explain how this relates to Carmichael's theorem. However, there seems to be a discrepancy between the derived result and the actual value given by Carmichael's theorem. This is eventually resolved by realizing that the theorem only holds for powers of odd primes, not powers of 2.
Whovian
In an attempt to prove a statement about the residues of a certain sequence mod ##10^n##, I've derived something which seems to be in direct violation of Carmichael's theorem. Of course, this can't be right, so can someone either explain what bit of my reasoning is wrong or why this isn't in violation of Carmichael's Theorem? First of all, let ##\lambda## be the Carmichael function, and let ##k## be coprime to 2 and 5.

First of all, notice that, by Euler's theorem, ##k^{4\cdot 5^{n-1}}\equiv1\pmod{5^n}## and ##k^{2^{n-1}}\equiv1\pmod{2^n}##. This makes it clear by induction that ##a\equiv b\pmod{4\cdot 5^{n-1}}\rightarrow k^a\equiv k^b\pmod{5^n}## and ##a\equiv b\pmod{2^{n-1}}\rightarrow k^a\equiv k^b\pmod{2^n}##.

Let ##n\ge2## and ##a\equiv b\pmod{10^n}##. Then, as ##\left.2^{n-1},4\cdot 5^{n-1}\right|10^n##, ##a\equiv b\pmod2^{n-1}## and ##a\equiv b\pmod5^{n-1}##, so ##k^a\equiv k^b\pmod{2^n}## and ##k^a\equiv k^b\pmod{5^n}##. Therefore ##k^a\equiv k^b\pmod{\mathrm{lcm}\left(2^n,5^n\right)}##, so ##k^a\equiv k^b\pmod{10^n}##.

Letting ##a=10^n## and ##b=0##, we get ##k^{10^n}\equiv k^0=1\pmod{10^n}##.

As this holds for all ##k## coprime to ##10^n##, this means ##\left.\lambda\left(10^n\right)\right|10^n##. (This should be obvious enough; I should be able to provide a proof if necessary.) However, as ##10^n## is not a power of 2, Carmichael's theorem tells us that ##\lambda\left(10^n\right)=\varphi\left(10^n\right)=4\cdot 10^{n-1}##, which doesn't divide ##10^n##.

Anyone know what's wrong here?

Whovian said:
Carmichael's theorem tells us that ##\lambda\left(10^n\right)=\varphi\left(10^n\right)=4\cdot 10^{n-1}##

Anyone know what's wrong here?

According to Wikipedia, for ##n\geq4## $$\lambda(10^n)=\text{lcm}\left(\lambda(2^n), \lambda(5^n)\right)=\text{lcm}\left(\frac{1}{2}\varphi(2^n), \varphi(5^n)\right)=\ldots=5\cdot10^{n-2},$$ and everything is right with the universe?

1 person
Ah. "A power of an odd prime, twice the power of an odd prime, and for 2 and 4."

*Collides hand with forehead to indicate frustration with self*

## 1. What is Carmichael's theorem?

Carmichael's theorem, also known as the Carmichael function, is a number theory theorem that gives the smallest positive integer that satisfies a particular property for a given number. It is named after the mathematician Robert Carmichael.

## 2. What is the property that Carmichael's theorem satisfies?

The property that Carmichael's theorem satisfies is that for any integer n, the value of the Carmichael function of n is equal to the value of Euler's totient function of n, where Euler's totient function calculates the number of positive integers less than n that are relatively prime to n.

## 3. How is Carmichael's theorem useful?

Carmichael's theorem is useful in number theory and cryptography as it helps in finding the smallest positive integer that satisfies certain equations, which can be used in encryption and decryption algorithms.

## 4. Can Carmichael's theorem be violated?

No, Carmichael's theorem cannot be violated as it is a mathematical theorem that has been proven to be true for all integers. However, it may appear to be violated in certain situations due to incorrect calculations or assumptions.

## 5. Are there any real-world applications of Carmichael's theorem?

Yes, Carmichael's theorem has practical applications in cryptography, specifically in the RSA encryption algorithm, where it is used to ensure the security of the encryption process.

• General Math
Replies
4
Views
1K
• General Math
Replies
1
Views
1K
• General Math
Replies
1
Views
2K
• General Math
Replies
2
Views
4K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
943
• Precalculus Mathematics Homework Help
Replies
1
Views
1K
• General Math
Replies
3
Views
2K
• Precalculus Mathematics Homework Help
Replies
4
Views
889
• Precalculus Mathematics Homework Help
Replies
1
Views
1K