2
$\begingroup$

If $n$ is a positive integer $\ge4$ then there exists a prime $p$ such that $n=p\cdot2^{k}+a$ where $k \ge 1$, $a<2^{k}$.

For example:

$333 = 41\cdot2^3 + 5$

$461 = 3\cdot2^7 + 77$

Work-in-Progress Proof:

Select $k$ so that $2^k \le n$ and $2^{k+1} > n$, i.e. $2^k * 2 > n$.

Divide $n$ by $2^k$ so that $n = 2^k + a$, $a < 2^k$ by the division algorithm.

So $n = 2*2^{k-1} + a$, 2 is prime ($p=2$), $k \ge 1$, and $a < 2^k$.

$\endgroup$
10
  • $\begingroup$ On what grounds do you think this is true? $\endgroup$ Nov 19, 2013 at 8:11
  • $\begingroup$ @Gerry I have verified it for 4 <= n <= 1000000. $\endgroup$
    – Jason
    Nov 19, 2013 at 8:14
  • 4
    $\begingroup$ divide $n$ by $2$ until you get a quotient of $2$ or $3$. $\endgroup$
    – mercio
    Nov 19, 2013 at 8:14
  • $\begingroup$ Is it true for 30? $\endgroup$
    – hhsaffar
    Nov 19, 2013 at 8:14
  • $\begingroup$ @hhsaffar: yes, 30 = 7*2^2 + 2, 30 = 3*2^3 + 6. $\endgroup$
    – Jason
    Nov 19, 2013 at 8:18

1 Answer 1

1
$\begingroup$

I'm sorry: I'm trying to add a comment, but I can't do it.

I do not know if I misunderstood something: if $n\geq 4$ is odd then $\exists ! k,\ k\in \mathbb N$ such that $2^k< n < 2^{k+1} $. This means $n= 2^k + a$ with $a < 2^k$ (if not we will have $n\geq 2^{k=1}$). For the even case, we can use a really similar line of reasoning ($n=2^{k_n}\cdot m$ with $m$ odd). In particular, in each case, we have $p=1$.

$\endgroup$
5
  • $\begingroup$ Please explain a little more the even case. $\endgroup$
    – user37238
    Nov 19, 2013 at 8:42
  • $\begingroup$ $n=2^{k_n}\cdot m$ with $m$ odd. So we know that $m=2^{k_m}+a_m$ with $a_m< 2^{k_n}$. Define $a_n= 2^{k_n}\cdot a_m$. We have that $a_n< 2^{k_n+k_m}$ and $n=2^{k_n+k_m}+ a_n$. $\endgroup$ Nov 19, 2013 at 8:48
  • $\begingroup$ Sorry, I made a typo mistake: $a_m< 2^{k_m}$. $\endgroup$ Nov 19, 2013 at 8:50
  • $\begingroup$ Ok thanks, there is still a problem, is $1$ a prime number... $\endgroup$
    – user37238
    Nov 19, 2013 at 8:53
  • $\begingroup$ No it is not a real problen. Can you see it? HINT: if $a<2^{k-1}$ no problem, if $2^{k-1}\leq a < 2^{k}$ reuse the same construction. $\endgroup$ Nov 19, 2013 at 9:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .