Prime divisors of form $4k+3$

For discussing Olympiad Level Number Theory problems
User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am
Prime divisors of form $4k+3$

Unread post by Thanic Nur Samin » Sat Jan 14, 2017 10:47 pm

Let $m$ be a positive integer. Prove that the sequence $\{a_n\}=2^nm+1$ contains infinitely many prime divisors of the form $4k+3$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Someone
Posts:6
Joined:Wed Sep 14, 2016 11:45 pm

Re: Prime divisors of form $4k+3$

Unread post by Someone » Sun Jan 15, 2017 1:06 am

Can m be any positive integer?

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Prime divisors of form $4k+3$

Unread post by Thanic Nur Samin » Sun Jan 15, 2017 4:12 pm

Someone wrote:Can m be any positive integer?
$m$ is a fixed positive integer. So yes, it can be any positive integer.
You can prove this only for odd $m$ and it would be proved for all $m$. Why?
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Prime divisors of form $4k+3$

Unread post by Thanic Nur Samin » Sun Jan 15, 2017 8:20 pm

Clearly, we can assume that $m$ is odd. So $a_1=2m+1$ which is of the form $4k+3$.

Let $2m+1=p_1^{e_1}p_2^{e_2}\ldots p_s^{e_s}$.

For the sake of contradiction, let the prime divisors of the form $4k+3$ which doesn't divide $a_1$ be finite, and let them be $q_1,q_2\ldots q_t$.

Now, take $N=p_1^{e_1}p_2^{e_2}\ldots p_s^{e_s}q_1q_2\ldots q_t$

So, $2^{\phi(N)}m+1\equiv 2m+1(\text{mod }N)$

From this we get that, $p_i^{e_i}||2^{\phi(N)}m+1$

And $q_i \nmid 2^{\phi(N)}m+1$

So, $\displaystyle \dfrac{2^{\phi(N)}m+1}{2m+1}$ only has divisors of the form $4k+1$. By letting $\phi(N)=F$,

$$\dfrac{2^Fm+1}{2m+1}\equiv 1 (\text{mod }4)$$

$$\Rightarrow 1\equiv 2^Fm+1\equiv 2m+1\equiv 3(\text{mod }4)$$

Which is a contradiction. Therefore there must exist infinitely many prime divisors of form $4k+3$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply