4
$\begingroup$

I'm working with a proof in a discrete structures CS course, and I am a little confused by how to build up some logic for the argument. Currently we're working with symbolic logic, the problem statement is:

"For all integers n, if n is an odd integer, then $ 3n^2$ is also an odd integer."

So far I know I can build this problem by stating the two following things:

  1. Prove all odd numbers, multiplied by $3$ remain odd. (how can I go about proving this?)
  2. Prove all odd numbers square also remain odd.

What would be the best way about proving this? Would it be simpler to prove all numbers multiplied by an odd number remain odd (since an odd number squared is still being multiplied by an odd number)

I'm not really looking for a solution to be handed to me, I just feel a little stuck on where to go from here, and would like some direction on what to do next.

Thanks ahead of time guys!

$\endgroup$
3
$\begingroup$

Consider that any odd number $x$ can be written as, for some integer $n$ $$x=2n+1.$$ So, if you had, for instance two odd $x_1$ and $x_2$, you could say $$x_1=2n_1+1$$ $$x_2=2n_2+1.$$ When you multiply these expressions, can you see how we would express the result in following form $$x_1x_2=2(\text{some integer})+1$$ and hence show the product is odd?

$\endgroup$
2
$\begingroup$

The definition of "odd" is "not divisible by 2". You can see that multiplying an odd number by 3 and squaring preserves oddness by manipulating the prime factorization, which will still contain no powers of 2.

$\endgroup$
  • $\begingroup$ It's worth noting that this only applies to integers; by this definition, $\sqrt{2}$ is odd, meaning the product of two "odd" numbers $\sqrt{2}\cdot \sqrt{2}=2$ is even! $\endgroup$ – Milo Brandt Nov 1 '14 at 20:40
  • $\begingroup$ A positive real number has a prime factorization if and only if it is an integer (at least if we assume the exponents of the primes are nonnegative integers). $\endgroup$ – Matt Samuel Nov 1 '14 at 20:42
2
$\begingroup$

Any odd number $n$ can be written as $2p+1$.

$3n^2$ = $3(2p+1)^2$

=$3(4p^2+4p+1)$

The term in parenthesis is odd, since $4p^2$ and $4p$ are both even for any value of $p$.

$3$ times an odd number is odd.

$\endgroup$
0
$\begingroup$

Probably the simplest proof you can make for this:

  • Let $n \in \mathbb{N}$ be odd.
  • Thus, $2 \not \mid n$.
  • Thus, $2 \not \mid n^2$.
  • We also note $2 \not \mid 3$, and thus, $2 \not \mid 3n^2$.

This proof essentially makes heavy use of the fact that if $d \mid ab$, then $d \mid a$ or $d \mid b$. The contrapositive of that claim is if $d \not \mid a$ and $d \not \mid b$, then $d \not \mid ab$.

(I recognize this post is old, but I felt like this proof is simpler and more intuitive, so hopefully people will appreciate this alternate proof as well.)

$\endgroup$

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.