30^239 = (31 - 1)^239 = (раскладываем в бином Ньютона, например) = (-1)^239 + 31*A A - какое-то целое число
Т.к. 30^239 = -1 + 31*A, то остаток от деления на 31 числа 30^239 совпадает с остатком от деления -1 на 31, т.е. равен 30
Еще можно сослаться на малую теорему Ферма: 30^(31-1) дает остаток 1 при делении на 31, тогда (30^240)=(30^30)^8 дает также остаток 1 при делении на 31. Тогда 30^239 дает остаток 30.
0 votes Thanks 1
danil4157
А как тогда доказать, что 30^239 + 239^30 — составное число?
danil4157
А как тогда доказать, что 30^239+30^239 — составное число?
nelle987
Что за питерские задачи? 30^239+30^239 делится на 2. 239^30 дает остаток 1 при делении на 39 (м.т.Ф., например). Тогда 239^30+30^239 дают такой же остаток при делении на 31, что и 30+1
Answers & Comments
Verified answer
30 = 31 - 130^239 = (31 - 1)^239 = (раскладываем в бином Ньютона, например) = (-1)^239 + 31*A
A - какое-то целое число
Т.к. 30^239 = -1 + 31*A, то остаток от деления на 31 числа 30^239 совпадает с остатком от деления -1 на 31, т.е. равен 30
Еще можно сослаться на малую теорему Ферма: 30^(31-1) дает остаток 1 при делении на 31, тогда (30^240)=(30^30)^8 дает также остаток 1 при делении на 31. Тогда 30^239 дает остаток 30.
239^30 дает остаток 1 при делении на 39 (м.т.Ф., например). Тогда 239^30+30^239 дают такой же остаток при делении на 31, что и 30+1