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

  • Thread starter Whovian
  • Start date
  • #1
647
3
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?
 

Answers and Replies

  • #2
575
76
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?
 
  • Like
Likes 1 person
  • #3
647
3
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*
 

Related Threads on This appears to be in direct violation of Carmichael's theorem.

  • Last Post
Replies
3
Views
2K
Replies
2
Views
606
Replies
1
Views
527
Replies
8
Views
935
Replies
1
Views
522
Replies
6
Views
2K
Replies
12
Views
2K
  • Last Post
Replies
1
Views
3K
Replies
2
Views
6K
  • Last Post
Replies
3
Views
11K
Top