Архив задач олимпиады по математике и криптографии

Квадратное уравнение с остатком

Найдите натуральное число не превосходящее 77, если известно, что остатки от деления числа на 77 и 96 равны соответственно 71 и 73.

  • Решение

    • Решение

    По условию

    x²=77n+71, x²=96m+73, m,n∈N.       (1)

    Приравняв правые части, найдем

    77n-96m=2   n=(96m+2)/77=m+(19m+2)/77. t∈Z.

    Перебором или с помощью алгоритма Евклида легко найти, что m0=8. Итак, m=77t+8. Подставим это выражение во второе уравнение (1):

    x2=96*77t+73.

    Поскольку

    x²≤77² заключаем, что t=0

  • Ответ

    • Ответ

    29