2

The following is a supposedly true claim, and I came across it in the Coursera course Introduction to Mathematical Thinking (Assignment 7/7) as part of an explanation by the instructor to the proof why $\sqrt{3}$ was irrational. The line that perplexes me goes like this:

If 3 divides the square of some x ∈ ℕ without a remainder, then 3 also divides x without a remainder.

How do we know that this is true for all squared natural numbers?

peterh
  • 2,683
malasi
  • 99
  • 4
    It follows from the fact that $3$ is prime – gd1035 Jul 13 '18 at 19:06
  • 1
    "If 3 divides the square of any $x\in \Bbb N$ without a remainder": this is poorly written, it should be some $x$. – Arnaud Mortier Jul 13 '18 at 19:06
  • 4
    Every number can be written in one of the forms $3n,3n+1,3n+2$. Just look at what happens if you square each type – lulu Jul 13 '18 at 19:06
  • This question was voted down to -1 when I came across it. This looks like a perfectly fine question to me; please don't vote it down without leaving an explanation. – Tanner Swett Jul 13 '18 at 19:12

2 Answers2

4

It does not hold only for squared natural numbers. It simply results from this more general result:

Euclid's lemma: If a prime $p$ divides a product of natural numbers, it divides at least one of the factors.

As in the present case there's only a repeated factor…

Bernard
  • 175,478
  • Thank you, I am reading about it, but need some time to understand it. Can I just ask you if lemmas are something that mathematicians learn by heart at the beginning, or one is actually supposed to understand their proofs? – malasi Jul 13 '18 at 19:33
  • A lemma , usually, is a preparatory results which is used in the proof of another result. Some lemmas are actually fundamental results for their domain, such as Euclid's lemma in arithmetic. A generalisation is known a Gauß' lemma, which asserts that if a number $n$ (not necessarily prime) divides a product $xy$, and $n$ is coprime to $x$, then $nˆdivides the other factor. – Bernard Jul 13 '18 at 19:43
1

If $x$ is not a multiple of 3, then either $x=3k+1$ or $x=3k+2$

For $x= 3k+1$, we get $x^2 = 9k^2+6k+1 = 3(3k^2+2k)+1$

For $x= 3k+2$, we get $x^2 = 9k^2+12k+4 = 3(3k^2+2k+1)+1$

As you notice, in either case $x^2$ is not a multiple of $3$

Thus is $x^2$ is a multiple of $3$, then $x$ must be a multiple $3$

Mohammad Riazi-Kermani
  • 68,728