Why do we apply the Euclidean Division, b divided by 3?

[evinda]

Hey!
I am looking at the following exercise:
"Prove that $\forall n \in \mathbb{N}$ the number $17 \cdot 3^{2n+1}+41 \cdot n^2 \cdot 3^{n+1}+2$ " is not a square of an integer."

We do it like that:
$a(n)= 17 \cdot 3^{2n+1}+41 \cdot n^2 \cdot 3^{n+1}+2=3 \cdot (17 \cdot 3^{2n}+41 \cdot n^2 \cdot 3^{n})+2$.
We suppose that $a(n)=b^2$,for a $b\in \mathbb{Z}$
Applying the Euclidean Division,$b$ divided by $3$ gives us $b=3k+r, r\in \{0,1,2\}$.
So,$b^2=(3k+r)^{2}$
For $r=0 , b^2=9k^2=3 \cdot 3k^2$,so the remainder is equal to $0$.
For $r=1 , b^2=9k^2+6k+1=3(3k^2+2k)+1 $,so the remainder is equal to $1$.
For $r=2 , b^2=9k^2+12k+4=3(3k^2+4k+1)+1 $,so the remainder is equal to $1$.

So,the remainder of $b^2$ divided by $3$,cannot be $2$ at any case..So,it cannot be $a(n)=b^2$.

But...Why do we apply the Euclidean Division,$b$ divided by $3$ ??

 

[I like Serena]

Hey!
I am looking at the following exercise:
"Prove that $\forall n \in \mathbb{N}$ the number $17 \cdot 3^{2n+1}+41 \cdot n^2 \cdot 3^{n+1}+2$ " is not a square of an integer."

We do it like that:
$a(n)= 17 \cdot 3^{2n+1}+41 \cdot n^2 \cdot 3^{n+1}+2=3 \cdot (17 \cdot 3^{2n}+41 \cdot n^2 \cdot 3^{n})+2$.
We suppose that $a(n)=b^2$,for a $b\in \mathbb{Z}$
Applying the Euclidean Division,$b$ divided by $3$ gives us $b=3k+r, r\in \{0,1,2\}$.
So,$b^2=(3k+r)^{2}$
For $r=0 , b^2=9k^2=3 \cdot 3k^2$,so the remainder is equal to $0$.
For $r=1 , b^2=9k^2+6k+1=3(3k^2+2k)+1 $,so the remainder is equal to $1$.
For $r=2 , b^2=9k^2+12k+4=3(3k^2+4k+1)+1 $,so the remainder is equal to $1$.

So,the remainder of $b^2$ divided by $3$,cannot be $2$ at any case..So,it cannot be $a(n)=b^2$.

But...Why do we apply the Euclidean Division,$b$ divided by $3$ ??

I am not familiar with the expression "Euclidean Division,$b$ divided by $3$".
However, I do see what was intended.
The results are taken modulo 3.

Since
$$a(n) \equiv 2 \pmod 3$$
for any $n$,
and since
$$b^2 \equiv 0,1 \pmod 3$$
for any $b$,
it follows that
$$a(n)\ne b^2$$
for any $n$ and for any $b$.

 

[evinda]

I am not familiar with the expression "Euclidean Division,$b$ divided by $3$".
However, I do see what was intended.
The results are taken modulo 3.

Since
$$a(n) \equiv 2 \pmod 3$$
for any $n$,
and since
$$b^2 \equiv 0,1 \pmod 3$$
for any $b$,
it follows that
$$a(n)\ne b^2$$
for any $n$ and for any $b$.

I haven't understood why we take $b=3k+r$ and then find from this $b^2$..

 

[I like Serena]

I haven't understood why we take $b=3k+r$ and then find from this $b^2$..

Any $b$ can be written as a multiple of 3 plus either 0, 1, or 2.

The reason to do so, is to find the remainder of $b^2$ modulo 3 (the remainder when dividing by 3).

 

[I like Serena]

Btw, I suspect you are learning this as part of a course in abstract algebra.
But this is really a Number Theory problem, so I am moving it there.

 

[Deveno]

I haven't understood why we take $b=3k+r$ and then find from this $b^2$..

The reason why is that it is the smallest prime that offers us some insight into this problem (using oddness/evenness isn't particularly helpful, in this case, all that is tells us is:

Odd squared is odd
Even squared is even).

Now we only have 3 possible remainders upon division by 3: 0, 1 or 2. This becomes the 3 cases:

$b = 3k \implies b^2 = 9k^2$
$b = 3k+1 \implies b^2 = (3k+1)^2 = 3(3k^2 + 2k) + 1 = 3m + 1$

(for the integer $m = 3k^2 + 2k$).

$b = 3k+2 \implies b^2 = (3k+2)^2 = 3(3k^2 + 4k + 1) + 1 = 3m' + 1$.

The whole purpose is to use the fact that only 3 remainders are possible to reduce the INFINITE number of cases (every natural number) to just THREE cases.

One can also see that if the remainder is 2, that is $b = 3k+2$, letting $k' = k + 1$, we see that $b$ is of the form $3(k + 1 - 1) + 2 = 3(k + 1) - 3 + 2 = 3k' - 1$, which makes it clear why division by "3" works so well, the remainder set is equivalent to:

$\{-1,0,1\}$

One can also express this as:

$ -1 \equiv 2\text{ (mod }3)$

This is a "common trick" in problems about natural numbers: to consider the same problem as a problem about integers, and then consider the equivalence classes modulo $p$ (where $p$ is prime). When $p = 2$, this is called "the arithmetic of parity" or "reasoning by odd and even cases".

Convince yourself (experiment a little, half the fun in math comes from "fooling around") that (modulo $p$ for an odd prime) we get only "half as many squares" as there are (non-zero) remainders. Such numbers are called "quadratic residues", and form an important part of number theory. For example, the quadratic residues modulo 5 are:

1, and 4.

So, if reducing mod 5, we find a certain expression is 2 or 3, we could likewise argue it is not a perfect square.

 

[evinda]

The reason why is that it is the smallest prime that offers us some insight into this problem (using oddness/evenness isn't particularly helpful, in this case, all that is tells us is:

Odd squared is odd
Even squared is even).

Now we only have 3 possible remainders upon division by 3: 0, 1 or 2. This becomes the 3 cases:

$b = 3k \implies b^2 = 9k^2$
$b = 3k+1 \implies b^2 = (3k+1)^2 = 3(3k^2 + 2k) + 1 = 3m + 1$

(for the integer $m = 3k^2 + 2k$).

$b = 3k+2 \implies b^2 = (3k+2)^2 = 3(3k^2 + 4k + 1) + 1 = 3m' + 1$.

The whole purpose is to use the fact that only 3 remainders are possible to reduce the INFINITE number of cases (every natural number) to just THREE cases.

One can also see that if the remainder is 2, that is $b = 3k+2$, letting $k' = k + 1$, we see that $b$ is of the form $3(k + 1 - 1) + 2 = 3(k + 1) - 3 + 2 = 3k' - 1$, which makes it clear why division by "3" works so well, the remainder set is equivalent to:

$\{-1,0,1\}$

One can also express this as:

$ -1 \equiv 2\text{ (mod }3)$

This is a "common trick" in problems about natural numbers: to consider the same problem as a problem about integers, and then consider the equivalence classes modulo $p$ (where $p$ is prime). When $p = 2$, this is called "the arithmetic of parity" or "reasoning by odd and even cases".

Convince yourself (experiment a little, half the fun in math comes from "fooling around") that (modulo $p$ for an odd prime) we get only "half as many squares" as there are (non-zero) remainders. Such numbers are called "quadratic residues", and form an important part of number theory. For example, the quadratic residues modulo 5 are:

1, and 4.

So, if reducing mod 5, we find a certain expression is 2 or 3, we could likewise argue it is not a perfect square.

Nice,thank you! :)