Застрял на задаче из теории чисел. Нужно найти все целые n такие, что выражение (2n^2 + 3) / 5 является целым числом. Понимаю что нужно смотреть на делимость, но не могу сообразить как правильно расписать условие. Пробовал через остатки, но запутался. Помогите пожалуйста с решением или хотя бы с подходом.
Нужно чтобы 5 делило 2n^2 + 3, то есть 2n^2 + 3 ≡ 0 (mod 5), откуда 2n^2 ≡ -3 ≡ 2 (mod 5), то есть n^2 ≡ 1 (mod 5).
n^2 ≡ 1 (mod 5) выполняется когда n ≡ 1 (mod 5) или n ≡ 4 (mod 5), то есть n ≡ ±1 (mod 5).
Ответ: все целые n вида n = 5k + 1 или n = 5k - 1, где k - произвольное целое число.
Проверяй брутфорсом остатки от деления n на 5. Остатки могут быть 0, 1, 2, 3, 4. Подставь каждый в 2n^2 + 3 и смотри что получается по модулю 5:
n ≡ 0: 0 + 3 = 3. Не делится.
n ≡ 1: 2 + 3 = 5 ≡ 0. Делится!
n ≡ 2: 8 + 3 = 11 ≡ 1. Не делится.
n ≡ 3: 18 + 3 = 21 ≡ 1. Не делится.
n ≡ 4: 32 + 3 = 35 ≡ 0. Делится!
Итого: n ≡ 1 (mod 5) или n ≡ 4 (mod 5).
n = 5k +/- 1. Все.
Мне кажется нужно подставить несколько чисел и посмотреть закономерность, например n=1 дает (2+3)/5=1 это целое, n=2 дает (8+3)/5=2,2 не целое, n=4 дает (32+3)/5=7 целое, n=6 дает (72+3)/5=15 целое... Видимо что то связанное с кратностью 5 +/- 1, но точно не уверен
Задача решается в рамках теории сравнений (конгруэнций), которую систематически изложил Гаусс в "Арифметических исследованиях" 1801 года. Кольцо вычетов Z/5Z содержит пять элементов, и квадраты в нем принимают значения {0, 1, 4}. Условие делимости 2n^2 + 3 на 5 сводится к поиску тех классов вычетов n mod 5, при которых 2[n]^2 + [3] = [0] в Z/5Z. Решение: [n] = [1] или [n] = [4], что соответствует n ≡ ±1 (mod 5).
Спасибо! Момент с тем что 2^(-1) ≡ 3 (mod 5) я не додумался применить, отсюда и путался. Все встало на место.