Form of the divisors

For discussing Olympiad Level Number Theory problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Form of the divisors

Unread post by tanmoy » Tue Mar 03, 2015 7:17 pm

Let $n$ be a positive integer.Show that all divisors of $4n^{2} + 1$ have the form $4k + 1$ for some
integer $k$.
"Questions we can't answer are far better than answers we can't question"

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm

Re: Form of the divisors

Unread post by Fm Jakaria » Wed Mar 04, 2015 2:40 pm

It suffices to show that all prime divisors $p$ of $4n^2+1$ is of the form $4k+1$. This is obvious because $p$ must be odd and has $-1$ as a quadratic residue.
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Form of the divisors

Unread post by Phlembac Adib Hasan » Thu Mar 05, 2015 7:55 pm

@tanmoy, I suppose you were expecting a detailed ans? Ignore this post, if that's not the case.

It can be proved if $p|x^2+y^2$ and $p\not | x,y$, then $p=4k+1$ for some $k$.
Let $x^2+y^2\equiv 0\pmod p$
$\Longrightarrow -x^2\equiv y^2\pmod p$
$\Longrightarrow (-x^2)^{\frac {p-1}{2}}\equiv (y^2)^{\frac{p-1}{2}}\pmod p$
$\Longrightarrow (-1)^{\frac{p-1}{2}}x^{p-1}\equiv y^{p-1}\pmod p$
$\Longrightarrow (-1)^{\frac{p-1}{2}}\equiv 1\pmod p\quad[\text{Fermat's little theorem}]$
But it means $\dfrac{p-1}2$ must be even. (Because $(-1)^{\text{odd}}=-1$). So $2|\frac{p-1}{2}\Longrightarrow 4 |p-1$
Also learn about quadratic residues, if you haven't (already)
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply