Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I'm trying disprove this statement. Well, I'm pretty sure it's wrong because it doesn't work when $a = 0$ . I'm just not sure if all I need to do is give that counterexample, or if there is a way to make a general disproof.

$$\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$$

I'm having a little trouble proving this one as well:

If an integer $a$ is of the form $5x+1$ for some integer $x$, then $a$ is of the form $25m+1$ for some integer $m$

For this statement I don't really know how to go about it, I've been stuck for a while now. Any help would be appreciated!

share|improve this question
1  
Your second statement seems to be missing something, as $\,a=5\cdot 1+1\ne 25\cdot k +1\,\,,\,\,\forall\,\,k\in\Bbb Z\,$ , shows... –  DonAntonio Mar 7 '13 at 1:17
    
What do you mean it doesn't work when $a=0$? –  Grumpy Parsnip Mar 7 '13 at 1:19
1  
Note that 0 doesn't divide any integer. –  vonbrand Mar 7 '13 at 1:22
    
$a=9$ and $b=12$ is another counterexample. –  Metin Y. Mar 7 '13 at 1:24
2  
@vonbrand $0$ divides $0$ –  Thomas Andrews Mar 7 '13 at 1:37

3 Answers 3

up vote 1 down vote accepted

To answer the "proof strategy" part of your question, to disprove a statement of the form $\forall a\,\forall b\,P(a,b)$ one counterexample $(a,b)$ is sufficient (although as it was pointed out in the comments, your proposed counterexample does not work, so you should use something like DonAntonio's instead.)

The negation of $\forall a\,\forall b\,P(a,b)$ is $\exists a\,\exists b\,\neg P(a,b)$, rather than $\forall a\,\forall b\,\neg P(a,b)$, so if the latter is what you mean by "general disproof" then no, a general disproof is not required (nor is it possible in this case.)

share|improve this answer

$$4\mid 6^2\,\,\wedge\,\,4\le 6\ldots$$

share|improve this answer

The stated property holds true for $\rm\,b\,$ iff $\rm\,b\,$ is a prime power.

Theorem $\ $ If $\rm\ 1 < b\in \Bbb N\ $ then $\rm\,b\,$ is prime power $\rm\iff \forall a\in\Bbb N\!:\,\ a\le b,\ a\mid b^2\Rightarrow\:a\mid b$

Proof $\ (\Rightarrow)\ $ If $\rm\,b\! =\! p^n$ is a prime power, $\rm\:a\le p^n,\ a\mid p^{2n}\!\Rightarrow a=p^j,\ j\le n\Rightarrow a\mid p^n\!=b$.

$(\Leftarrow)\,\ $ If $\rm\,b\,$ is not a prime power then its prime factorization has at least two primes $\rm\,p\neq q,\,$ say $\rm\, b = p^j q^k n,\,\ p,q\nmid n,\,$ and $\rm\ p^j\! <\! q^k.\:$ Thus $\rm\,b = p^j(q^kn) = cd,\,\ c<d,\,\ c\nmid d.\:$ Thus for $\rm\,a=c^2\,$ we have $\rm\:a\mid b^2\,$ i.e. $\rm\, c^2\!\mid (cd)^2,\:$ and $\rm\,a\le b\,$ i.e. $\rm\,c^2\!<cd\,$ by $\rm\,c<d,\:$ and $\rm\,a\nmid b,\,$ i.e. $\rm\,c^2\!\nmid cd\,$ by $\rm\,c\nmid d.$

Remark $\ $ Notice that the proof shows how to construct a counterexample for any natural $\rm\,b > 1\,$ not a prime power. DonAntonio's counterexample is the special case $\rm\ b = p^j q^k n = 2\cdot 3 = cd$.

Note that the proof implicitly employs uniqueness of factorization in a couple places. Firstly, to infer that the factors of $\rm\,p^{2n}$ all have form $\rm\,p^j,\,$ and, secondly, to infer that $\rm\,p\nmid q,n\:\Rightarrow\: p\nmid q^kn.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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