To find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$

Question

How do we find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$ ? The primes certainly satisfy this condition ; what other integers do satisfy this condition ?

Answer 1

I understand the question as follows.

Find all (positive) integers $n$ such that for all integers $a$, $$ \text{if $n \mid a (a-1)$, then either $n \mid a$ or $n \mid a-1$.} $$

Prime powers $n$ clearly satisfy this condition.

So suppose $n = s t$, with $s, t > 1$ coprime. Since $s$ is invertible modulo $t$, clearly there is $k$ such that $t \mid k s + 1$. (Take $-k$ to be the inverse of $s$ modulo $t$.)

Take $a = k s + 1$. Then $n \mid a (a-1)$, as $t$ divides $a$ and $s$ divides $a-1$. But clearly $s$ does not divide $a$ (otherwise it would divide $1$), and $t$ does not divide $a - 1$ (same). So $n$ does not divide $a$ nor $a-1$.

So $n$ must be a prime power.