Question

Find a composite number \(n\) such that \(n | (a^n-a)\) for all \(a\)

Answer 1

\(\Large a^n=a \mod n
\\ \text{we basicly know }
\\ \Large a^{\phi (n)}=1 \mod n \)
\(\Large a^{\phi (n)+1}=a \mod n
\\ \text{so we need n that satisfiy }

\\ \Large \phi(n)+1=n \\ \Large \phi(n)=n-1\\ \text{which means n need to be prime }\\\text {hence no composite solution for n} \\ QED \square \)

Answer 2

Actually your "proof" shows that ALL prime numbers \(n\) divide \(a^n-a\) for all \(a\)

But it doesn't prove there cannot be composite numbers

Answer 3

Here's me trying to find an answer but can't seem to see how to take this further.

n is either even or odd, so I'm going to guess 50/50 shot that it's odd. \[\large n =2m+1\] Now we know n divides a^n-a for all a, so for every a there is some k we can multiply by n to get a^n-a. So k is a function of a, but instead of writing k(a) it will just be understood. So I'll write this all out as: \[\Large a^{2m+1}-a = k(2m+1)\] Here you can see why I made the choice to guess n was odd, it lets me factor this cleanly into: \[\Large a(a^m+1)(a^m-1)= k(2m+1)\] From here I make notice of a couple things, k is still a function of a, so I'm going to exploit that, but it's also a fairly arbitrary proportionality constant. Let's look at the left hand side closer, if we reason through when a is odd or a is even we will find that the left hand side is always even! So we can tuck that into our k(a). But there's more I'd like to put into it. We also know that we can represent a geometric series as \[\Large s = \frac{a^m-1}{a-1}\] So we can use this fact to doctor up our k(a) function even further: \[\Large k(a) = 2 * a * (a-1)s * t(a) \] So here quick recap, we have k(a) encapsulating the fact that the left is even, a multiple of a, and since it's completely arbitrary we're saying that it also has (a-1)*s in it. But not only that, we're throwing in an extra proportionality constant t which is still a function of a to allow us to continue making adjustments if we need to, like for the geometric series to work out. Plugging this in we have: \[\Large a(a^m+1)(a^m-1) = 2 a (a-1)s* t (2m+1) \\ \Large \frac{a(a^m+1)(a^m-1)}{a(a-1) s} =2 t(2m+1) \\ \Large a^m-1 = 2t(2m+1)\] I don't know if this is entirely legal with the geometric series part or if I should have left it in since it has m in it, in fact I think it must be wrong since this leads to a contradiction that a^m is always odd when clearly it can be either even or odd. But fun to play with, I'll come back tomorrow probably to see what I can do, since there's still the t function and geometric series for even a will always be odd while geometric series for odd a can be either, so that's worth looking into as well. =)

Answer 4

So if we expand our geometric series we'll have: \[\Large s = 1+a+a^2+ \cdots + a^{m-1}\] Clearly if a is even, then the sum is even. But what about for odd a? The parity depends on the number of terms since all the a^x terms are all odd when a is odd, we are looking at odd+odd = even, even+odd = odd, so it's oscillating back and forth. To stop this ship from sinking we have to decide how we want to play, and so the easiest approach might be to just put restrictions on (m-1). Let's make it even so there will be an even number of terms that way the geometric series is even regardless. We can come back to this point if we find that we get stuck and try to allow (m-1) to be odd so that when a is odd the series is odd and when a is even the series is even.

Maybe instead of stunting ourselves to reworking a lot of the problem, let's just let \[\Large m-1 = 2r+\alpha\] an we can set alpha to 0 or alpha to 1 depending on how we want to look at it. I'm gonna start scribbling and see what more nonsense I can squeeze out.

Answer 5

Ok I've removed the s, since it really didn't do anything. Nothing changes since the (a-1) part was still just an aspect of k(a) being an arbitrary function of a. Plugging it all in I am at: \[\large (a^m+1)(1+a+a^2+ \cdots + a^{m-1})=2t(4r+2 \alpha+3)\] remembering that \[\alpha = 0 \implies m \ odd \\ \alpha = 1 \implies m \ even\] Meh I'm still stuck, but this path I've led down has really given me more ideas of where to look. Maybe I should have initially started out with \[\Large n = (2u + \mu)(2v+\nu)k\] Afterall, it is composite and I can probably refine this a bit based on what we've seen here. Hmm. Oh well maybe later.

Answer 6

http://m.wolframalpha.com/input/?i=Table%5B%28b%5E%28561%29-b%29+%28mod+561%29%2C%7Bb%2C2%2C100%7D%5D&x=0&y=0


\(\large \begin{align} \color{black}{561=3\times 11\times 17
}\end{align}\)

Answer 7

http://www.wolframalpha.com/input/?i=Table%5B%28b%5E%28561%29-b%29+%28mod+561%29%2C%7Bb%2C2%2C100%7D%5D&dataset=

Answer 8

counter example for marki's proof

Answer 9

Yeah but the fun is in how you get the answer! Anyone can just look them up from here! http://en.wikipedia.org/wiki/Carmichael_number

Answer 10

yeslol, i got the liar numbers for fermat

Answer 11

I was trying to see if I could derive this formula for a subset of the Carmichael numbers, since apparently some of them follow this pattern: \[\Large (6k+1)(12k+1)(18k+1)\] as long as those three factors are prime. I have no idea how you could show that lol.

Answer 12

that works! xD

Answer 13

we want to show below holds whenever the factors 6k+1, 12k+1, 18k+1 are prime : \[a^{n} \equiv a \pmod{(6k+1)(12k+1)(18k+1)}\]

which is equivalent to system of congruences of smaller moduli :

\[a^{n}\equiv a \pmod{6k+1}\\a^{n} \equiv a\pmod{12k+1}\\a^{n} \equiv a\pmod{18k+1}\]

we can prove each of this congruence is true by appealing to Fermat's little thm :
\[a^{6k+1}\equiv a \pmod{6k+1}\\a^{12k+1}\equiv a \pmod{12k+1}\\\\a^{18k+1}\equiv a \pmod{18k+1}\\\]

Answer 14

Wow! when k=1 we get the ramanujan number :
n = (6*1+1)(12*1+1)(18*1+1) = 7*13*19 = 1729

Answer 15

oh i relalized my try was stupid a bit lol

Answer 16

this is the right congruence
\(\Large a^{\phi (n)+1}=a \mod n
\\ \text{so we need n that satisfiy }

\\ \Large (\phi(n)+1|n) \\ \)

hmmm

Answer 17

eh never mind both doesn't work anyway xD