факт (возможно ложный): простое число вида p=4k+1

[rightways]

Дано простое число $p$ вида $4k+1$ и натуральное число $a$. Известно, что $(a,p)=1$. Докажите, что существует натуральное число $n$ такое что $(n,a)=1$ и $p|n^2+a^2$ .

[Sonic86]

rightways в сообщении #1015350 писал(а):

$p|n^2+a^2$ .

$n^2+a^2\equiv 0 \pmod p \Rightarrow n\equiv \pm ai\pmod p$, где $i\equiv\sqrt{-1}\pmod p$ существует, поскольку $p\equiv 1\pmod 4$.

rightways в сообщении #1015350 писал(а):

Известно, что $(a,p)=1$.

Это условие излишне.

Непонятно, что эта задача делает в олимпиадном разделе

[rightways]

к сожалению не понимаю числа Гаусса.

[Sonic86]

rightways в сообщении #1015356 писал(а):

к сожалению не понимаю числа Гаусса.

Не понимаю вопрос, не могу ответить.
Почему разрешимо сравнение $t^2\equiv -1\pmod p$ для $p=4k+1$ знаете? Этого вполне достаточно.

[rightways]

да, но есть условие $(a,n)=1$ оно мне мешает.

[Sonic86]

rightways в сообщении #1015366 писал(а):

да, но есть условие $(a,n)=1$ оно мне мешает.

Пусть дан класс вычетов $r \pmod p$ и число $a$. Как найти $n:n\equiv r \pmod p$ такое, что $\gcd(a,n)=1$?

[Andrey A]

rightways в сообщении #1015366 писал(а):

да, но есть условие $(a,n)=1$ оно мне мешает.

$n\equiv at \mod p$ Что тут мешает?
Такие задачи очень удобно решать цепными дробями. Возьмем простой модуль $137=11^2+4^2$. Разложим дробь $\frac{11}{4}=2,1,3$. Тогда знаменатель "зеркальной" дроби $3,1,2,2,1,3=\frac{137}{37}$ и есть нужное Вам $t$: $37^2\equiv -1\mod 137$. Если взять теперь $a=5$, то $n=37\cdot 5 \mod137=48$.
$5^2+48^2=137\cdot 17$
$(5,48)=1$
И любое другое по $\mod137$ не кратное пяти. Теперь заклюют меня что выложил с потрохами, хотя решения симметричными дробями в учебниках не встречал.

[rightways]

Нда..
Оказалось можно найти даже такое простое $n$...

-- 16.05.2015, 21:26 --

И условие $(a,p)=1$ неизлишнее

[Andrey A]

Andrey A в сообщении #1015412 писал(а):

Тогда знаменатель "зеркальной" дроби $3,1,2,2,1,3=\frac{137}{37}$ и есть нужное Вам $t$...

Подробнее об этом здесь: http://dxdy.ru/post1077031.html#p1077031 Подзаголовок "ПАЛИНДРОМЫ".