Well the following post isn't really a question but actually a verification of a proof of a problem. I would be highly grateful if you would just check my proof. Here goes the problem and the proof:-

Let $N $ $\epsilon $ $ \mathbb{Z}^+$. Now, we know that if N is composite then $m$ divides $N$ where $1\le m \le \sqrt{N}$. I wanted to see that if $m_1$, $m_2$ $\epsilon $ $ \mathbb{Z}^+$ such that $m_1\le \sqrt{N} <m_2$ and $m_1 \nmid N$, then $m_2\nmid N$. Here $m_1$ is any natural number $\le \sqrt{N}$ and $m_2$ is any natural number $> \sqrt{N}$ but $<N$.

PROOF:- Let $m_1$, $m_2$ $\epsilon $ $ \mathbb{Z}^+$ such that $m_1\le \sqrt{N} <m_2$ and $m_1 \nmid N$. Let us assume that $m_2|N$. $\Rightarrow$ $N$ = $\alpha m_2$ and $N$ = $\beta m_1 + \gamma$ where $0<\gamma<m_1$. From the above equations, we can say that:- $\alpha m_2$ = $\beta m_1 + \gamma$ where $0<\gamma<m_1$.$\Rightarrow$ $\beta m_1 = \alpha m_2 - \gamma$ where $0<\gamma<m_1$ or $\beta m_1 = \alpha^{\prime} m_2 + \gamma^{\prime}$ where $0<\gamma^{\prime}<m_2$. $\Rightarrow$ $m_2\nmid\beta m_1$ or $m_2\nmid(N-\gamma)$ $\Rightarrow$ $(N-{\gamma})= \alpha^{\prime\prime} m_2 + \beta^{\prime}$ where $0 < \beta^{\prime}<m_2$ or $N= \alpha^{\prime\prime} m_2 + \beta^{\prime} + \gamma^{\prime}$ or $N= \alpha^{\prime\prime\prime} m_2 + \beta^{\prime\prime} $ where $0< \beta^{\prime\prime} < m_2$ $\Rightarrow$ $m_2 \nmid N$. But this is contradiction to our assumption. Hence $N$ is a prime number.

Note:- Here $\mathbb{Z}^+$ is the set all non zero positive integers only.

  • $\begingroup$ You have not stated the problem. Despite (or more probably because) of the many symbols that you use, there is a lack of clarity. You presumably mean that if $N$ is composite, then there is an $m$ such that $\dots$. Surely we should not allow $m=1$. Are $m_1$ and $m_2$ any numbers such that $m_1\le \sqrt{N} <m_2$ and such that $m_1$ does not divide $N$? Then how are we to conclude anything about $m_2$? Are you only trying to prove that if $N$ has no divisors $d$ with $1<d\le \sqrt{N}$ then $N$ is prime? $\endgroup$ – André Nicolas Mar 20 '12 at 18:22
  • $\begingroup$ I'm sorry, I don't understand what you are trying to prove. Set $N=91, m_1=2, m_2=13$ - whether 91 is divisible by 13 is not determined by the fact that it is odd. $\endgroup$ – Mark Bennet Mar 20 '12 at 18:22
  • $\begingroup$ @ Andre Nicolas. You are right about my thought process. That's exactly what I thought. I can see it in many examples but tried to prove it here. $\endgroup$ – andrew james Mar 20 '12 at 18:54
  • $\begingroup$ @ Mark Bennet. If we set $N$ = 91, then $\sqrt{91} = 9.53.......$. Now, $7$ does divides $91$ and well this shows that $91$ is composite. Also, I don't think that this proof depends on the fact that a number is odd or even. $\endgroup$ – andrew james Mar 20 '12 at 18:58
  • $\begingroup$ Andrew, you then need to specify that your condition is true for all integers less than the square root. And it would help at the beginning if you would state that you are trying to prove than N is prime. André has given an answer which reflects my best guess as to what you mean. $\endgroup$ – Mark Bennet Mar 20 '12 at 19:04

I will rephrase what I think you are trying to prove, in language close to the one that you used.

Theorem: Let $N$ be an integer greater than $1$. If $N$ has no divisor $m$ such that $1<m\le \sqrt{N}$, then $N$ is prime.

Proof: Suppose to the contrary that $N$ is not prime. Then there are integers $a$ and $b$ such that $ab=N$ and neither $a$ nor $b$ is equal to $1$. By assumption, $a >\sqrt{N}$ and $b>\sqrt{N}$. It follows that $ab>(\sqrt{N})(\sqrt{N})$. So $ab>N$, contradicting our assumption that $ab=N$.


As others have noted in the comments, this is false.

Regarding where the error in your purported proof lies, that's hard to tell because you didn't provide any justifications for any of the steps. The last $\gamma'$ should be $\gamma$, but I'm not sure that makes a difference, since even if it were $\gamma'$ I don't see any justification for the claim that $\beta''\ne0$.

Generally it's a good idea for this sort of thing to try out some simple examples before diving into an ocean of symbols in which you can easily drown. Using the example from Mark's comment, with $N=91$, $m_1=2$ and $m_2=13$, we have $\alpha=7$, $\beta=45$, $\gamma=1$, $\alpha'=6$, $\gamma'=12$, $\alpha''=\alpha'$, $\beta'=\gamma'$ (the last two are immediate; it's not clear why you introduced new variables with identical values here), $\alpha'''=7$, $\beta''=0$. But even before you started looking for a proof, a moment's reflection could have shown you that the claim can't possibly be true, since it would imply that no composite number has divisors greater or equal to its square root, whereas in fact every composite number has such divisors.

  • $\begingroup$ Thank you very much for catching my mistake. $\endgroup$ – andrew james Mar 20 '12 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.