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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

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

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: This appears to be in direct violation of Carmichael's theorem.

Loading...

**Physics Forums - The Fusion of Science and Community**