7
$\begingroup$

Okay, here is how I begin my proof:

Let $q$ and $r$ be odd integers, then $q = 2k+1$ and $r = 2m+1$, where $k,m \in Z$.

$q \times r = (2k+1)(2m+1) \implies q \times r = 4mk + 2k + 2m + 1 \implies q \times r = 2(2mk + k + m) + 1$

I would then conclude that $q \times r$ results in an odd number, because 2 times an integer with one added to it is, by definition, an odd number.


However, how can I conclude this? Is $(2mk + k + m)$ in fact an integer? How do I know if the product of any two integers is an integer; similarly, does adding any two integers yield another integer? Now, obviously, I have an intuitive notion that these are true, but is there a way to prove them?

Side note: I would also appreciate it if someone could critique my proof.

$\endgroup$
3
  • 6
    $\begingroup$ Note that you haven't used the hypothesis that the integers are different anywhere in the proof; and indeed that hypothesis isn't required. $\endgroup$
    – joriki
    Mar 14, 2013 at 17:40
  • $\begingroup$ You can just state that Z is closed under multiplication and addition. If you want to prove that, check out the proof for addition and multiplication here. $\endgroup$ Mar 14, 2013 at 18:40
  • 1
    $\begingroup$ The question in the second paragraph, "how do I know that the product of any two integers is an integer?", should be promoted to the title. The side-note request to assess the proof has a trivial answer: CORRECT! $\endgroup$
    – zyx
    Mar 14, 2013 at 18:40

3 Answers 3

6
$\begingroup$

Slightly more generally, note that multiplying $\rm\:m\, =\, k+an\:$ by any integer of the form $\rm\:1+bn\:$ doesn't change the remainder that $\rm\,m\,$ leaves when divided by $\rm\,n,\,$ i.e. the remainder stays = $\rm k,\,$ by

$$\rm (k+an)(1+bn)\, =\, k+n(a+b(k+an))$$

This is a special case $\rm\,j=1\,$ of $\rm\ mod\ n\!:\ \ \begin{eqnarray} x &\equiv&\,\rm k\\ \rm y &\equiv&\,\rm j\end{eqnarray}\ \Rightarrow\ xy\equiv\, k\, j,\ \ $ the Congruence Product Rule

That $\rm\: a+b(k+an)\in \Bbb Z\:$ follows from the fact that $\rm\:a,b,c\in \Bbb Z\:\Rightarrow\: a + b\,c\in \Bbb Z,\:$ since integers are closed under multiplication, thus $\rm\:bc\in \Bbb Z,\:$ and also under addition, hence $\rm\:a + bc\in\Bbb Z.\:$ Finally, that $\rm\,\Bbb Z\,$ is closed under the operations of addition and multiplication follows from the recursive definitions of addition and multiplication in Peano arithmetic. Your proof is correct.

$\endgroup$
2
$\begingroup$

Your proof is fine, and it is true that the product of two integers is also an integer. You can't prove this, as this is one of the axioms of integers.

I recommend that you now prove this:

Let $p\in \mathbb{Z}$ and $p^2$ even. Then $p$ is even.

Note this isn't the same as saying $p$ even $\Longrightarrow$ $p^2$ even, which is also true.

$\endgroup$
5
  • 1
    $\begingroup$ What axioms of integers ? $\endgroup$ Mar 14, 2013 at 17:45
  • 1
    $\begingroup$ You can't prove that the integers are closed under multiplication? That's fresh. $\endgroup$ Mar 14, 2013 at 18:40
  • 1
    $\begingroup$ Yes I'm sorry, that was a mistake. I was using the set of "axioms" from a calculus book. Still, like Math Gems said, using the peano axioms, you can prove the closure. My point was integers are closed under addition and multiplication, so the OP didn't have to worry about that part being incorrect. Still, I should have been more careful. $\endgroup$
    – Orlando
    Mar 14, 2013 at 18:45
  • $\begingroup$ @NikBougalis: Technically it is conceptually easier to axiomatize the naturals based on its semiring properties than Peano's axioms. I am certain most mathematics teachers can easily come up with the rules based on the semiring structure unlike PA. In any case, all axioms are by definition provable, but when lay people say "provable" they do not include self justification, in which case the axioms of PA are also not provable. $\endgroup$
    – user21820
    Jun 22, 2015 at 4:31
  • $\begingroup$ @NikBougalis: The bottom line is that without any inference rules and axioms beyond those of first-order logic, you cannot get the naturals. Worse still, even first-order PA has uncountable models. ZFC makes naturals a countable set by defining countable in terms of naturals, so everything eventually boils down to having to understand naturals first before trying to axiomatize it. Proofs themselves are a natural number of symbols in a sequence... $\endgroup$
    – user21820
    Jun 22, 2015 at 4:35
2
$\begingroup$

A simple way of doing this is as follows. Let $p, q \in \mathbb{Z}$ be odd. Then suppose that $2 | pq$. Then, as $2$ is prime, we must have that $2 |p $ or $2 |q$.But either of these cases is impossible as both $p$ and $q$ are odd.

$\endgroup$
6
  • $\begingroup$ I think your proof assumes that if a prime number divides a product, it necessarily divides one of the factors. This is provable (via the Fundamental Theorem of Arithmetic), but you'd have to prove it. $\endgroup$ Oct 27, 2014 at 15:13
  • $\begingroup$ Of course it does. I assumed that the student knew this fact. Maybe that was a mistake. $\endgroup$ Oct 28, 2014 at 0:24
  • $\begingroup$ I was thinking that, but it strikes me as less obvious than the proposition you are trying to prove. (Apparently, this is exactly Euclid's lemma.) $\endgroup$ Oct 28, 2014 at 4:31
  • $\begingroup$ Really? To me it is more clear. Primes are defined with that algebraic property $\endgroup$ Oct 28, 2014 at 5:16
  • 1
    $\begingroup$ Obviousness is, I suppose, in the eye of the beholder. In fact, I proved Eulid's lemma (in my head) with the Fundamental Theorem, but later learned that the standard proof for the Fundamental Theorem depends on the lemma. A non-circular proof requires Bézout's identity, which I find unintuitive. $\endgroup$ Oct 28, 2014 at 6:53

You must log in to answer this question.

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