Наша следующая идея: сократить числитель и знаменатель
![$s$ $s$](https://dxdy-03.korotkov.co.uk/f/6/f/9/6f9bad7347b91ceebebd3ad7e6f6f2d182.png)
и
![$t$ $t$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f4f4e395762a3af4575de74c019ebb582.png)
числа
![$b_2$ $b_2$](https://dxdy-01.korotkov.co.uk/f/8/0/5/8050505667919156622832a0c9b5671c82.png)
, используя (15), и затем уже тестировать по модулю
![$41$ $41$](https://dxdy-02.korotkov.co.uk/f/5/7/f/57f24c92347b553ce05216fb62cb408682.png)
или другого простого числа, причём проверять, что
![$t(s-16 t)$ $t(s-16 t)$](https://dxdy-01.korotkov.co.uk/f/0/1/4/014c116f97e1ffb77fd40f61dbd5035c82.png)
является квадратом после деления числа
![$t$ $t$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f4f4e395762a3af4575de74c019ebb582.png)
на чётные степени простых делителей числа
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
.
Перед этим неплохо было бы получить утверждение (15) для простых делителей
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
и
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
числа
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
.
Сократив числа
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
,
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
и
![$a_4$ $a_4$](https://dxdy-04.korotkov.co.uk/f/b/b/e/bbeda48c4e54184c28225916e2d34fa382.png)
на их наибольший общий делитель, будем считать их взаимно-простыми (не попарно).
Из (5) следует:
(15.1)
Пусть простое число
![$p=5$ $p=5$](https://dxdy-04.korotkov.co.uk/f/3/c/a/3ca231d3f2808398c86dfb41c007113382.png)
является делителем числа
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
, и
![$p^{k_3}$ $p^{k_3}$](https://dxdy-02.korotkov.co.uk/f/5/6/9/569bbb75b46f67fed25afd19ecd23a5282.png)
является наибольшей степенью простого числа
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, на которую делится
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
.
Пусть
![$k_3>1$ $k_3>1$](https://dxdy-01.korotkov.co.uk/f/8/7/2/8723b75dc459c2e01d6b30c808aedc5882.png)
.
Тогда число
![$k_3-1$ $k_3-1$](https://dxdy-03.korotkov.co.uk/f/6/5/2/652d46633318d57fd69ae984dcd88c1582.png)
делится на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
, и
![$p^{(k_3-1)/3}$ $p^{(k_3-1)/3}$](https://dxdy-04.korotkov.co.uk/f/3/5/c/35cfe1d2d9873bebdee8bf0232c9dc3582.png)
является наибольшой степенью простого числа
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, на которую делится либо
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
, либо
![$a_4$ $a_4$](https://dxdy-04.korotkov.co.uk/f/b/b/e/bbeda48c4e54184c28225916e2d34fa382.png)
, а другое число из этих двух не делится на
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
.
В самом деле, из (5) следует, что
![$10 (a_2 a_4)^3$ $10 (a_2 a_4)^3$](https://dxdy-01.korotkov.co.uk/f/c/4/c/c4cbfb5ca6c7abe9f33e5b899934c48582.png)
делится на
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
, следовательно одно из чисел
![$a_2^3$ $a_2^3$](https://dxdy-02.korotkov.co.uk/f/d/e/4/de4bb9b8dd1a0c2b04843dbddac2894c82.png)
и
![$a_4^3$ $a_4^3$](https://dxdy-02.korotkov.co.uk/f/1/6/f/16f4321c034e8527c550518827c231fb82.png)
делится на
![$p^{k_3-1}$ $p^{k_3-1}$](https://dxdy-03.korotkov.co.uk/f/a/6/2/a62a17e8157aa9bdf8f59b9884ec53b682.png)
, поскольку только одно из них делится на
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, вследствие взаимной простоты чисел
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
,
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
и
![$a_4$ $a_4$](https://dxdy-04.korotkov.co.uk/f/b/b/e/bbeda48c4e54184c28225916e2d34fa382.png)
.
Если, например, число
![$a_2^3$ $a_2^3$](https://dxdy-02.korotkov.co.uk/f/d/e/4/de4bb9b8dd1a0c2b04843dbddac2894c82.png)
делится на
![$p^{k_3-1}$ $p^{k_3-1}$](https://dxdy-03.korotkov.co.uk/f/a/6/2/a62a17e8157aa9bdf8f59b9884ec53b682.png)
, то на бОльшую степень
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
оно не делится, иначе левая часть равенства (5) делилась бы на
![$p^{k_3+1}$ $p^{k_3+1}$](https://dxdy-01.korotkov.co.uk/f/8/a/b/8ab76fd754485b796ea9f43ae095773082.png)
, а правая часть - нет, поскольку
![$a_2^5+4 a_4^5$ $a_2^5+4 a_4^5$](https://dxdy-04.korotkov.co.uk/f/3/a/8/3a8dc4b5a7bb2d8f3e96f44a0470d84b82.png)
не делится на
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
.
(15.2)
Пусть простое число
![$p=2$ $p=2$](https://dxdy-02.korotkov.co.uk/f/9/0/2/90264925fb137831c8f410cd14c75cff82.png)
является делителем числа
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
, и
![$p^{k_3}$ $p^{k_3}$](https://dxdy-02.korotkov.co.uk/f/5/6/9/569bbb75b46f67fed25afd19ecd23a5282.png)
является наибольшей степенью простого числа
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, на которую делится
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
.
Пусть
![$k_3>1$ $k_3>1$](https://dxdy-01.korotkov.co.uk/f/8/7/2/8723b75dc459c2e01d6b30c808aedc5882.png)
.
Тогда либо число
![$k_3-1$ $k_3-1$](https://dxdy-03.korotkov.co.uk/f/6/5/2/652d46633318d57fd69ae984dcd88c1582.png)
делится на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
, и
![$p^{(k_3-1)/3}$ $p^{(k_3-1)/3}$](https://dxdy-04.korotkov.co.uk/f/3/5/c/35cfe1d2d9873bebdee8bf0232c9dc3582.png)
является наибольшой степенью простого числа
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, на которую делится число
![$a_4$ $a_4$](https://dxdy-04.korotkov.co.uk/f/b/b/e/bbeda48c4e54184c28225916e2d34fa382.png)
, либо
![$k_3+1$ $k_3+1$](https://dxdy-02.korotkov.co.uk/f/9/2/d/92d2b5fbd96df5ba2f380e202781759a82.png)
делится на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
, и
![$p^{(k_3+1)/3}$ $p^{(k_3+1)/3}$](https://dxdy-04.korotkov.co.uk/f/f/b/f/fbf15c1659665eba8a113f6ef4a598dc82.png)
является наибольшой степенью простого числа
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, на которую делится число
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
.
В самом деле, из (5) следует, что
![$10 (a_2 a_4)^3$ $10 (a_2 a_4)^3$](https://dxdy-01.korotkov.co.uk/f/c/4/c/c4cbfb5ca6c7abe9f33e5b899934c48582.png)
делится на
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
, следовательно одно из чисел
![$a_2^3$ $a_2^3$](https://dxdy-02.korotkov.co.uk/f/d/e/4/de4bb9b8dd1a0c2b04843dbddac2894c82.png)
и
![$a_4^3$ $a_4^3$](https://dxdy-02.korotkov.co.uk/f/1/6/f/16f4321c034e8527c550518827c231fb82.png)
делится на
![$p^{k_3-1}$ $p^{k_3-1}$](https://dxdy-03.korotkov.co.uk/f/a/6/2/a62a17e8157aa9bdf8f59b9884ec53b682.png)
, поскольку только одно из них делится на
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, вследствие взаимной простоты чисел
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
,
![$a_3$ $a_3$](https://dxdy-04.korotkov.co.uk/f/7/8/8/788998aa37ce7b850be242e21214e15982.png)
и
![$a_4$ $a_4$](https://dxdy-04.korotkov.co.uk/f/b/b/e/bbeda48c4e54184c28225916e2d34fa382.png)
.
Если число
![$a_4^3$ $a_4^3$](https://dxdy-02.korotkov.co.uk/f/1/6/f/16f4321c034e8527c550518827c231fb82.png)
делится на
![$p^{k_3-1}$ $p^{k_3-1}$](https://dxdy-03.korotkov.co.uk/f/a/6/2/a62a17e8157aa9bdf8f59b9884ec53b682.png)
, то на бОльшую степень
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
оно не делится, иначе левая часть равенства (5) делилась бы на
![$p^{k_3+1}$ $p^{k_3+1}$](https://dxdy-01.korotkov.co.uk/f/8/a/b/8ab76fd754485b796ea9f43ae095773082.png)
, а правая часть - нет, поскольку
![$a_2^5+4 a_4^5$ $a_2^5+4 a_4^5$](https://dxdy-04.korotkov.co.uk/f/3/a/8/3a8dc4b5a7bb2d8f3e96f44a0470d84b82.png)
не делится на
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
.
Если число
![$a_2^3$ $a_2^3$](https://dxdy-02.korotkov.co.uk/f/d/e/4/de4bb9b8dd1a0c2b04843dbddac2894c82.png)
делится на
![$p^{k_3-1}$ $p^{k_3-1}$](https://dxdy-03.korotkov.co.uk/f/a/6/2/a62a17e8157aa9bdf8f59b9884ec53b682.png)
, то правая часть равенства (5) делится на
![$p^{k_3+2}$ $p^{k_3+2}$](https://dxdy-02.korotkov.co.uk/f/1/d/8/1d8e7c21a2eca882bb65eedabb20f5f582.png)
,
поскольку
![$a_2^5+4 a_4^5$ $a_2^5+4 a_4^5$](https://dxdy-04.korotkov.co.uk/f/3/a/8/3a8dc4b5a7bb2d8f3e96f44a0470d84b82.png)
делится на
![$4$ $4$](https://dxdy-03.korotkov.co.uk/f/e/c/f/ecf4fe2774fd9244b4fd56f7e76dc88282.png)
, следовательно
![$a_2^3$ $a_2^3$](https://dxdy-02.korotkov.co.uk/f/d/e/4/de4bb9b8dd1a0c2b04843dbddac2894c82.png)
делится на
![$p^{k_3+1}$ $p^{k_3+1}$](https://dxdy-01.korotkov.co.uk/f/8/a/b/8ab76fd754485b796ea9f43ae095773082.png)
, но на бОльшую степень
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
оно не делится, иначе левая часть равенства (5) делилась бы на
![$p^{k_3+3}$ $p^{k_3+3}$](https://dxdy-02.korotkov.co.uk/f/5/0/0/500ab75ede14fd5adfae96c3af0db32682.png)
, а правая часть - нет.
Продолжение следует.