Question

Довести, що 11^288 – 1 ділиться без залишку на 323

Answer 1

Малая теорема ферма :

Если p - простое число и a - целое число, такое, что a, p  взаимно простые , то  ${a}^{p-1}\equiv 1~(mod \ p)$

В  нашем же случае

${a}^{p-1}-1\equiv 1-1~(mod \ p)$

$a^{p-1} - 1\equiv 0 (\mod p)$

Заметим что

323 = 340 - 17 = 17 · (20-1) = 17 · 19

Проверяем по отдельности , делимость на 19  и 17

1.1Проверим делится ли $11^{288} -1$  на   19  

Раскладываем  $11^{288} -1$  по формуле разностей квадратов

$11^{288} -1 = (11^{144} +1)(11 ^{144}-1) = (11^{144} +1)(11 ^{72}+1) (11 ^{72}-1)= \\\\ = (11^{144} +1)(11 ^{72}+1) (11 ^{36}+1)(11 ^{36}-1)= \\\\=(11^{144} +1)(11 ^{72}+1) (11 ^{36}+1)(11 ^{18}+1)(11^{18}-1)$

Рассмотрим скобку в которой   $11^{18} -1$  , можно легко заметить что к ней применима теорема Ферма

$11^{18} -1 = 11^{19-1}-1\equiv 0(\mod 19) \Rightarrow \boxed{*~ 11^{288}-1 \equiv 0(\mod 19) }$  

1.2Теперь проверим  делится ли  $11^{288} -1$ на 17

Раскладываем  $11^{288} -1$  по формуле разностей кубов

$11^{288} - 1 = (11^{96} -1 )(11^{192} + 11^{96}+1) =\\\\= (11^{32}-1)(11^{64}+ 11^{32} +1) (11^{192} + 11^{96}+1)$

Разложим  $11^{32}-1$   по формуле разностей квадратов

$11^{32} -1 = (11^{16 } +1)(11^{16}-1)$

Рассмотрим множитель     $11^{16}-1$  ,  к нему также применима теорема Ферма

$11^{16} -1 = 11^{17-1}-1\equiv 0(\mod 17) \Rightarrow \boxed{**~ 11^{288}-1 \equiv 0(\mod 17) }$

Таким образом :

Из  *   и  **   мы доказали , что   $11^{288}-1 \equiv 0(\mod 323)$

#SPJ1