Register to reply

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

by Whovian
Tags: appears, carmichael, theorem, violation
Share this thread:
Whovian
#1
Mar20-14, 03:32 PM
P: 642
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?
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
gopher_p
#2
Mar20-14, 06:26 PM
P: 423
Quote Quote by Whovian View Post
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?
Whovian
#3
Mar24-14, 03:56 PM
P: 642
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*


Register to reply

Related Discussions
Direct Integration vs. Green's Theorem Calculus & Beyond Homework 7
If time travel is possible does it allow for violation of the no clone theorem Quantum Physics 15
Violation of Bell's Theorem Quantum Physics 199
Noether theorem + CP violation -> Energy is not conserved? Beyond the Standard Model 16
Carmichael Numbers Calculus & Beyond Homework 1