nが3の倍数ならばn^nも3の倍数であるのでn^n+1は3で割り切れない. [これは剰余演算を出すまでもないでしょう.]
またnを3で割った余りが1のとき, すなわちn≡1 (mod3)ならばn^n+1=2 (mod3)なので, n^n+1は3で割り切れない.
最後にnを3で割った余りが2のとき, すなわちn≡(-1) (mod 3)ならばn^n+1=0[nが偶数のとき], 2[nが奇数のとき].
となるので, ℓを自然数としてn=3(2ℓ)-1と表される数, すなわちnは6で割って余りが5の正の整数であればよい.
訂正しきれていないので, 下に差し替えてください.
***
n^n+1≡0 (mod 3)[nが奇数のとき], 2 (mod 3)[nが偶数のとき].すなわちnは6で割って余りが5の正の整数であればよい.
となるので, n≡(-1) (mod 3)かつn≡(-1) (mod 2)なのでn≡(-1) (mod 6),
***
最後はx≡a (mod m), x≡a (mod m)ならばx≡a (mod nm)を使っています.
ごちゃごちゃしているので以下に書き直します.
***
nが3の倍数ならば, n^nも3の倍数なのでn^n+1は3で割り切れない.
次に, nを3で割った余りが1のとき, すなわちn≡1 (mod 3)ならばn^n+1≡2 (mod 3)となるから, n^n+1は3で割り切れない.
最後に, nを3で割った余りが2のとき, すなわちn≡(-1) (mod 3)のとき,
nが偶数ならばn^n+1≡2 (mod 3)となるのでn^n+1は3で割り切れない.
nが奇数ならばn^n+1≡0 (mod 3)なのでn^n+1は3で割り切れる.
以上から条件を満たすnはn≡(-1) (mod 3)かつn≡(-1) (mod 2)
⇔n≡(-1) (mod 6)⇔n≡5 (mod 6)
[自明ではないので, この考察がないと減点されるでしょう]
すなわちnは6で割って余りが5となるような正の整数であればよい.
[あるいは次のように構成する. nは任意の自然数ℓに対しn=6ℓ-1となるような数]
***
[ノート] n≡a (mod p), n≡a (mod q)ならばn≡a (mod pq) [p, qは互いに素な自然数]
n≡(-1) (mod 2)かつn≡(-1) (mod 3)
⇔n+1≡0 (mod 2), n+1≡0 (mod 3) [n+1が2でも3でも割り切れる]
⇔n+1≡0 (mod 6)
⇔n≡-1 (mod 6)
⇔n≡5 (mod 6)
[訂正] トンデモないミスをしているので訂正してください.
n^n+1=0[nが奇数のとき], 2[nが偶数のとき].
となるので, n≡(-1) (mod 3)かつn≡1 (mod 2)なのでn≡(-1) (mod 6), すなわちnは6で割って余りが5の正の整数であればよい.