場合 $n$ 擬素数であり、 $[n,a]=[n,a+1]=1$、その後 $(a+1)^n\equiv a^n +1 \pmod n$？
問題を見つけました（$[a,b]$ の公約数です $a,b$。）
場合 $n$ 擬素数であり、 $a$ そのような整数 $[n,a]=[n,a+1]=1$、それを示す
$$(a+1)^n\equiv a^n +1 \pmod n$$
提案： $a^n\equiv a\pmod n, \; (a+1)^n\equiv a+1\pmod n$。
私はその提案をフェルマーの小定理として認識していますが、それは次の場合に当てはまります。 $n$素数です。Mathematicaでいくつかのテーブルを作ろうとしましたが、アイデンティティが保持されていないようです。これは本当ですか、それとも私は何か間違いを犯していますか？
回答
Pseudoprimeの状態、
擬素数は、それらが満たす素数の特性に従って分類されます。
あなたの質問の問題は、どの特定のプロパティが使用されているかを明示的に述べていません $n$、しかし、プロパティは（たとえば、彼らの提案に基づいて）フェルマー擬素数であるように見えます。もしそうなら、フレーズ「$n$ 擬素数、...」は「もし $n$ ベースへのフェルマー擬素数です $a$ とベース $a + 1$、...」。
彼らの提案はその後真実になるでしょう $a^{n-1} \equiv 1 \pmod{n} \implies a^n \equiv a \pmod{n}$ そして $(a + 1)^{n-1} \equiv 1 \pmod{n} \implies (a + 1)^n \equiv a + 1 \pmod{n}$。これから、代用$a^n$ ために $a$ 2番目の合同の右側には、要求されたものが表示されます。 $(a + 1)^n \equiv a^n + 1 \pmod{n}$。