Олимпиада Туймаада по математике. Младшая лига. 2000 год

Существуют ли простые $p$ и $q$, большие 3, такие, что $p^2-1$ делится на $q$ и $q^2-1$ делится на $p$?

Комментарий/решение

Можно понять то что p неравно q.пусть p>q,тогда так как p,q нечётны p>q+1.С другой стороны,по условию (q+1)(q-1) делится на p,но ни один из сомножителей q+1 и q-1 на р не делится.Это доказывает что нт таких p и q.

Ответ: нет

$q=6k+1, 6k-1$

$(i)q=6k-1$

$p \mid (6k-1)^2-1$

$p \mid 12k(3k-1)$

$p \mid (12k-2)(6k-1)-2+6k+12k(3k-1)$

$p \mid 6k$

$p \nmid 6 \rightarrow p \mid k$

$lp=k$

$6lp-1=q$

$q \mid (\frac{q-1}{6l})^2-1$

$\frac{6k-2}{6l} \notin N$ $\blacksquare$

$(ii)q=6k+1$

$p \mid 12k(3k+1)$

$p \mid (12k+2)(6k+1)-2-6k-36k^2-12k$

$p \mid 6k$

$p \nmid 6 \rightarrow p \mid k$

$lp=k$

$6lp+1=q$

$6lp+1 \mid (p+1)(p-1)$

$6lp+1 \mid (6lp+1)(p-1)+(6l-1)(p-1)$

$6lp+1 \mid 6lp+1-6l-p$

$6lp+1 \mid 6l+p$

$6l+p \ne 0, -k(6lp+1) \rightarrow 6lp+1=6l+p$

$6l(p-1)=p-1 \rightarrow 6l=1 \rightarrow \varnothing $ $ $ $\blacksquare$