2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 08:26 
Дано простое число $p$ вида $4k+1$ и натуральное число $a$. Известно, что $(a,p)=1$. Докажите, что существует натуральное число $n$ такое что $(n,a)=1$ и $p|n^2+a^2$ .

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 08:35 
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$.
Это условие излишне.

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

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 08:51 
к сожалению не понимаю числа Гаусса.

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 09:15 
rightways в сообщении #1015356 писал(а):
к сожалению не понимаю числа Гаусса.
Не понимаю вопрос, не могу ответить.
Почему разрешимо сравнение $t^2\equiv -1\pmod p$ для $p=4k+1$ знаете? Этого вполне достаточно.

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 09:39 
да, но есть условие $(a,n)=1$ оно мне мешает.

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 11:20 
rightways в сообщении #1015366 писал(а):
да, но есть условие $(a,n)=1$ оно мне мешает.
Пусть дан класс вычетов $r \pmod p$ и число $a$. Как найти $n:n\equiv r \pmod p$ такое, что $\gcd(a,n)=1$?

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение15.05.2015, 11:31 
Аватара пользователя
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$ не кратное пяти. Теперь заклюют меня что выложил с потрохами, хотя решения симметричными дробями в учебниках не встречал.

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение16.05.2015, 18:24 
Нда..
Оказалось можно найти даже такое простое $n$...

-- 16.05.2015, 21:26 --

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

 
 
 
 Re: факт (возможно ложный): простое число вида p=4k+1
Сообщение16.12.2017, 21:38 
Аватара пользователя
Andrey A в сообщении #1015412 писал(а):
Тогда знаменатель "зеркальной" дроби $3,1,2,2,1,3=\frac{137}{37}$ и есть нужное Вам $t$...

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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group