整式が素数になるかどうかの問題です。剰余類を考えましょう。
《問題》
$4$個の整数
$n+1$、$n^3+3$、$n^5+5$、$n^7+7$
がすべて素数となるような正の整数$n$は存在しない。これを証明せよ。
（大阪大学2013 前期理系第３問）
《考え方》
何個か並べられた多項式の素数判定では、ほぼ確実にmodを使います。「$2$より大きい偶数でない」は素数であることの必要条件ですが、「$3$より大きい$3$の倍数でない」も素数であることの必要条件ですし、「$5$より大きい$5$の倍数でない」も素数であることの必要条件です。modで倍数判定するという操作において、$2$という素因数を特別視する必要性は本来存在しません。
modで整数を分類するという操作は整数に「色を塗っていく」ようなものだとイメージしてください。$2$で割った余りで分類するのであれば白と黒で塗り分ける感じです。$3$で割った余りで分類するのであれば白と黒と灰色、とか、赤、黄、青とか（何でも良いですが）で塗り分ける感じです。同じ色のグループで分けたものが「剰余類」です。偶奇で分けるという操作は物事を二分することで考えやすくするというメリットが大きいために多用されますが、modを考えるということを数字に色を塗ってグループ分けする操作であると考えれば、$2$という数字は決して特別ではありません。
本問では$\color{green}{4}$つの多項式の素数判定なので $\text{mod} \ \color{green}{4}$ を使いたいところですが、実は $\text{mod} \ 4$ では解決できません。そこで $\text{mod} \ 3$ を使います。
$n \equiv 0 \pmod{3}$ のとき $n^3+3$ は$3$より大きい$3$の倍数となるので素数にはなりません。従って $n \not\equiv 0 \pmod{3}$ が必要です。
$n \equiv 1 \pmod{3}$ のとき $n^5+5 \equiv 1+2 \equiv 0 \pmod{3}$ となり、$3$より大きい$3$の倍数となるので素数にはなりません。従って $n \not\equiv 1 \pmod{3}$ が必要です。
$n \equiv 2 \pmod{3}$ のとき $n+1 \equiv 2+1 \equiv 0 \pmod{3}$ となり、$n>2$ のとき$3$より大きい$3$の倍数となるので素数にはなりません。そこで $n=2$ のときを調べます。$2+1=3$（素数）、$2^3+3=11$（素数）、$2^5+5=37$（素数）となって上手くいきそうですが、$2^7+7=135=3^3 \cdot 5$ となるのですべてが素数になることはありません。従って $n \not\equiv 2 \pmod{3}$ が必要です。
結局、正の整数$n$は $n \not\equiv 0 \pmod{3}$ かつ $n \not\equiv 1 \pmod{3}$ かつ $n \not\equiv 2 \pmod{3}$ を満たす必要がありますが、このような正の整数$n$は存在しません。よって題意が示されました。
（コメント）
初見ではなかなか手を付けにくい問題ですが、合同式を使えばあっさりと解決できます。この問題が簡単だと感じられる方は、是非ご自分で本問のような問題を作ってみてください。整数に対する造詣が深まること請け合いです。
さて、解答例では $\text{mod} \ 3$ を利用しましたが、他の除数、例えば$5$などで $\text{mod} \ 5$ を考えてみるのはダメなのでしょうか？また $\text{mod} \ 6$ ではどうでしょうか？
$\text{mod} \ 3$ が最適である理由は、まず何と言ってもカテゴリが少ないことでしょう。
例えば偶奇で分けて素数判定したいとします。問題文で与えられた$4$個の整数に対して$2$で割った余りは$0$、$1$のいずれかで高々$2$種類しかありません。$n \equiv 0 \pmod{2}$ を選べばすべて余りが$1$となり、偶数でないことは分かりますが、素数かどうかまでは判定できません。
ある整数を$3$で割った余りは$0$、$1$、$2$の高々$3$種類なので、$\text{mod} \ 3$ は $\text{mod} \ 2$ の次に場合分けがラクです。解答例の通り、与えられた$4$個の整数の素数判定が可能です。
私たちが目指しているのはあくまでも「素数判定」であって、「素数の発見」ではないということを肝に銘じておきましょう。素数判定とは言ってしまえば「素数である可能性を潰す」ということです。つまりある数の倍数になっているかどうかを調べることが（高校レベルで知り得る）素数判定のほぼ唯一の方法ですから、modを考えるときは、倍数となるものが多くなるような除数（法とも言います：$\text{mod} \ 3$ なら$3$のこと）を設定しなくてはなりません。つまり余りの数が与えられた整数の数を超えるような除数はそれほど有効ではないのです。（※本問では役に立ちませんが「（ある数が）もし素数なら$n$はこの形で表されるものに限る」という必要条件を導くときにmodを使うことはあります）
以上の点を踏まえた上で $\text{mod} \ 5$ を考えましょう。ある整数を$5$で割った余りは$0$、$1$、$2$、$3$、$4$の$5$種類で、与えられた$4$個の整数の数より多くなっています。この時点で何となく分類しきれないニオイが嗅ぎ取れます。実際、$n \equiv 1 \pmod{5}$ のとき、問題の$4$つの整数はいずれも$0$と合同にならず、$5$の倍数かどうか分からないので素数判定はできません。このことから「$4$つの整数がすべて素数になるとしたら $n=5k+1 $ の形に限る」ということは言えますが、状況はあまり進展しません。
個人的な見解ですが、「素数判定」と相性が良いのは $\text{mod} \ 3$ と $\text{mod} \ 6$ でしょう。本問では $\text{mod} \ 6$ も利用できるのですが、実質 $\text{mod} \ 3$ でやっていることと変わりません。
これも個人的な見解で、本問とはあまり関係が無いのですが、「平方数判定」と相性が良いのは $\text{mod} \ 3$ と $\text{mod} \ 4$、たまに $\text{mod} \ 5$ だと思っています。
いずれにせよ臨機応変に対応できなければならないですね。