0
$\begingroup$

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} 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 $.

PROOF:- Let $m_1$, $m_2$ $\epsilon $ $ \mathbb{Z}^+$ such that $m_1\le \sqrt{N} 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. From the above equations, we can say that:- $\alpha m_2$ = $\beta m_1 + \gamma$ where $0<\gamma.$\Rightarrow$ $\beta m_1 = \alpha m_2 - \gamma$ where $0<\gamma or $\beta m_1 = \alpha^{\prime} m_2 + \gamma^{\prime}$ where $0<\gamma^{\prime}. $\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} 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.

  • 0
    Andrew - I've posted some embarrassingly silly things in my time, b$u$t if I hadn't, I wouldn't have learned ...2012-03-20

2 Answers 2

3

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, 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$.

0

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.

  • 0
    Thank you very much for catching my mistake.2012-03-20