While experimenting with modulo arithmetic I came upon this slight extension to Fermat's Little Theorem (for which I have a proof).
$$\text{If a is a positive integer and p is prime and }\ge\text{ 5 then}$$
$$a^p \equiv a\pmod{3\times p} $$
I cannot believe this has remained unnoticed but I will ask anyway.
Is there any chance this is new?
This is certainly known, but it doesn't have a name.
More generally,
Lemma: If $q$ is prime and $n$ is any positive integer such that $q-1\mid n-1$ then: $$a^n\equiv a\pmod{q}$$ Proof: This can be proved by induction on $k=\frac{n-1}{q-1}$.
Let $n_k=1+(q-1)k$. Then $n_0=1$ and $a^{1}\equiv a\pmod{q}$.
Now, if $a^{n_k}\equiv a\pmod{q}$, then $$a^{n_{k+1}}=a^{n_k}a^{q-1}\equiv a\cdot a^{q-1}=a^q\equiv a\pmod{q}$$
Now the case when $p\geq 5$ is prime and $q=3$ means $a^{p}-a$ is divisible by $p$ and $3$, thus, by $3p$.
It is also divisible by $2$, so you really get:
$$a^{p}\equiv a\pmod{6p}$$
You also have that if $p>5$ with $p\equiv 1\pmod 4$ then $a^p\equiv a\pmod{30p}$.
The lemma lets you assert, for example, that $a^{13}\equiv a\pmod{2\cdot 3\cdot 5\cdot 7\cdot 13}$.
Try these problem by yourself first: 1. Given relatively prime integers $a, b, c$, if I tell you any three numbers $i, j, k$, can you tell me an integer $N$ such that all three holds simontaneously: $$ N \equiv i \mod a$$ $$N \equiv j \mod b$$ $$N \equiv k \mod c$$ ? Can you always give me such $N$ ?
As a concrete example, can you tell me a number $N$ such that $$N \equiv 5 \mod 7$$ $$N \equiv 2 \mod 5$$ $$N \equiv 10 \mod 11$$ ?
Can you generalize ?
Nice observation, but this is basically Chinese Remainder Theorem. (See the handout here for some nice and hard problems regarding this)
The $\mod p$ part is handled by Fermat's theorem, but the $\mod 3$ part is easily handled by observing $$ 2^{odd} \equiv 2 \mod 3$$ and $$1^{odd} \equiv 1 \mod 3$$.
In case you're feeling bad this turned out to be trivial, try this fun one if you didn't see it before: $2n$ divideds $\phi(a^n+1)$ for any integer $a, n$ with $gcd(a,n) = 1$
Actually by Fermat's little theorem, $3$ always divides $$a^3-a=a(a^2-1)$$
As $p-1$ is even for $p\ge3$ $$a^{p-1}-1$$ is divisible by $a^2-1$
Hence, $a^p-a$ will be divisible by $3$ and $p$ and consequently by lcm$(3,p)$
