# (Dis)prove that: $\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$

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!

-
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
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
@vonbrand $0$ divides $0$ –  Thomas Andrews Mar 7 '13 at 1:37

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.)

-

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

-

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

-