Take $n=561= 3 \cdot 11 \cdot 17$, checking is trivial. My proposal (not easy): prove that there is an infinite number of composite $n$ with $a^n \equiv a \mod n$ for all integers $a$.

I think the real problem here is: find a way to come up with the number 561. Also, do you have a solution for your variant? If it has a nice solution, we may add it.

Any such number must be a Carmichael Number, but I don't know if a problem Erdos couldn't resolve can be described as "not easy"

We want those squarefree $ n$ such that $ p - 1 |n - 1$ for all primes $ p|n$. We can try $ n = pqr$ a product of $ 3$ distinct primes, then we want $ p - 1|qr - 1,q - 1|rp - 1,r - 1|pq - 1$. Choose $ p = 3$, the first property becomes trivial for odd $ q,r$ and we want $ q - 1 | 3r - 1, r - 1|3q - 1$. Now write $ 3q - 1 = k(r - 1)$, so $ q = \frac {k(r - 1) + 1}{3}$, we are left with $ \frac {k(r - 1) - 2}{3} | 3r - 1$ or in other words $ 3| k(r - 1) - 2 | 9r - 3$. For big $ r$, this requires $ k \leq 9$. Lets try $ k=3$: We want a prime $ r$ such that $ 3r - 5 | 9r - 3$. This requires $ 3r-5 | 12$, simply giving $ r=17$ and we end up with $ q=11$.