Олимпиада имени Леонарда Эйлера 2021-2022 учебный год, I тур дистанционного этапа

Натуральные числа $n$ $(n > 1)$ и $k$ таковы, что для любого натурального делителя $d$ числа $n$ хотя бы одно из чисел $d+k$ и $d-k$ также является натуральным делителем числа $n$. Докажите, что число $n$ — простое. ( А. Голованов )

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

Начнем с того, что числа 1 и n - делители числа n, значит числа n-k и 1+k аналогично являются делителями данного числа. Так как все числа, кроме самого n, не превосходят n/2 мы получаем, что $n-k\leq n/2$ , отсюда $k\geq n/2.$

Но значит 1+k > n/2, значит k+1 = n,или k = n - 1. Рассмотрим, что у числа n, есть делитель d > 1. В таком случае одно из чисел d+n- 1 или d-n+1 обязано быть делителем числа n. Но данные числа не являются делителями, т. к d+n-1>n, а d-n+1<1. Исходя из этого, единственные делители числа n - это n и 1, следовательно n-простое

пусть числа 1 и n - делители числа n, значит числа n-k и 1+k тоже являются делителями данного числа. Все числа не большем n/2 , поэтому п-k < n/2 и k>n/2. получили что 1+k > n/2 имеем 2 варианта k+1 = n либо k = n - 1. Рассмотрим, что у числа n, есть делитель d > 1. В таком случае одно из чисел d+n- 1 или d-n+1 обязано быть делителем числа n. Но данные числа не являются делителями, т. к d+n-1>n, а d-n+1<1. Исходя из этого, единственные делители числа n - это n и 1, следовательно n-простое