Online Course Discussion Forum

IIB number theory problem 5.8

 
 
Picture of Claire Lee
IIB number theory problem 5.8
by Claire Lee - Thursday, 11 April 2024, 7:15 PM
 

Why does the number have to divisible by 9 for it to be a perfect square? 4 x 4 =16 and it isnt divisible by 9 but it still is a perfect square.

 
Picture of John Lensmire
Re: IIB number theory problem 5.8
by John Lensmire - Friday, 12 April 2024, 12:11 PM
 

You're correct that in general, a number doesn't need to be divisible by 9 to be a perfect square. But 5.8 is a little different. In fact, I'm a little confused about this being asked in terms of 5.8, so let's look at 4.6 as well. Both rely on the fact that a number is equivalent to the sum of its digits (mod 3) and (mod 9).

In Example 4.6 we prove that a 15-digit number made up of five 1s, five 2s, and five 3s is not a perfect square.

Here, the sum of the digits of the 15-digit number is 5+10+15 = 30, which is = 0 (mod 3) and = 3 (mod 9). Hence, the 15-digit number is divisible by 3 but not divisible by 9. Note this means that the number cannot be a perfect square because we know it's prime factorization has a 3 but not a 3^2.

In Example 5.8 we also use the sum of the digits, which is then 0+2+4+6+8 = 20, which is = 2 (mod 3). However, you can check that any square number is either 0 or 1 (mod 3), meaning that anything that is = 2 (mod 3) is NOT a perfect square.

Hope this helps! Let us know if you have additional questions or if I misinterpreted something.

Picture of Claire Lee
Re: IIB number theory problem 5.8
by Claire Lee - Friday, 12 April 2024, 12:40 PM
 

My question is why do we only use mod9 for the perfect square instead of using other mods like 4, 16, 25, 36.....? 

Even though the 15digit or 5digit number cannot be a perfect square of 3, it can be a perfect square of other numbers like 2,4,5,6,7,......


Picture of John Lensmire
Re: IIB number theory problem 5.8
by John Lensmire - Friday, 12 April 2024, 5:21 PM
 

In these two problems, (mod 9) and (mod 3) are natural to use because any number is equivalent to it's sum of digits. So, taking 5.8 as an example, even though there are 5! = 120 ways to rearrange the digits 0, 2, 4, 6, 8, the sum of the digits is ALWAYS 20. So we know that the number is 2 (mod 3) and (2 mod 9).

In general, however, there might be some trial and error in which mods to use. Further, remember that mods can give us restrictions (so they can be used to show something does NOT exist), but cannot be used to prove something does exist.

Let's take a basic example of 135 and ask is 135 a perfect square, meaning is there an integer k such that $k^2 = 135$. (Obviously the answer is no, but let's explore a bit).

Note if $k^2 = 135$ then

  • Mod 2: $k^2 \equiv 1 \pmod{2}$. Note this does imply that $k\equiv 1 \pmod{2}$, but is otherwise INCONCLUSIVE in determining if $135$ is a perfect square. (Because it is possible for a perfect square to be $\equiv 1 \pmod{2}$.)
  • Mod 3: $k^2 \equiv 1+3+5 \equiv 0 \pmod{3}$. Again, this does imply that $k\equiv 0 \pmod{3}$, but is otherwise INCONCLUSIVE in determining if $135$ is a perfect square.  (Because it is possible for a perfect square to be $\equiv 0 \pmod{3}$.)
  • Mod 9: $k^2 \equiv 1+3+5\equiv 0 \pmod{0}$, INCONCLUSIVE.
  • Mod 10: $k^2\equiv 5 \pmod{10}$, INCONCLUSIVE.
  • Mod 4: $k^2\equiv 3 \pmod{4}$. Here, note none of $0^2$, $1^2$, $2^2$, or $3^2$ are $\equiv 3 \pmod{4}$, so we can CONCLUSIVELY say that $k^2$ is NOT a perfect square.

If it helps, think of this as a proof by contradiction. If we assume $k^2 = 135$ then $k^2 \equiv 3 \pmod{4}$ but this is a contradiction.