It appears to be true for all $n$ from 1 to 100. Can anyone help me find a proof or a counterexample?
If it's true, my guess is that it follows from known classical results, but I'm having trouble seeing it.
In some cases, the prime factors congruent to 1 mod 3 are relatively large, so it's not as simple as "they're all divisible by 7" or anything like that.
It's interesting if one can prove that an integer of a certain form must have a prime factor of a certain form without necessarily being able to find it explicitly.
EDITED TO ADD: It appears that there might be more going on here!
$n^2-1$ usually has a prime factor congruent to 1 mod 2 (not if n=3, though!)
$n^3-1$ always has a prime factor congruent to 1 mod 3
$n^4-1$ always has a prime factor congruent to 1 mod 4
$n^5-1$ appears to always have a prime factor congruent to 1 mod 5.
Regarding $n^2-1$: If $n>3$, then $n^2-1=(n-1)(n+1)$ is a product of two numbers that differ by 2, which cannot both be powers of 2 if they are bigger than 2 and 4. Therefore at least one of $n-1,n+1$ is divisible by an odd prime.
Regarding $n^4-1$: If $n>1$, we factor $n^4-1$ as $(n+1)(n-1)(n^2+1)$. We claim that in fact, every prime factor of $n^2+1$ is either 2 or is congruent to 1 mod 4. If $p$ is an odd prime that divides $n^2+1$, then $-1$ is a square mod $p$, but the odd primes for which $-1$ is a square mod $p$ are precisely the primes congruent to 1 mod 4. It remains just to show that $n^2+1$ cannot be a power of 2. If $n$ is even this is obvious, and if $n=2k+1$ is odd, then $n^2+1=(2k+1)^2+1=4k^2+4k+2$ is 2 more than a multiple of 4.
Regarding $n^5-1$, I don't have a proof, but based on experimenting with a few dozen numbers, I conjecture that in fact, every prime factor of $n^4+n^3+n^2+n+1$ is either 5 or is 1 more than a multiple of 5.