# Number TheoryModular arithmetic problem

#### Economan

##### New member
Hi everyone,

I am new to the site so please let me know if I'm posting in the wrong place.

I am starting to teach myself number theory and would like a bit of help with a problem.

How would I go about showing "If m^2 = 0 (mod 3) then m = 0 (mod 3)"? I am then asked to deduce that root 3 is irrational.

If you could point me in the right direction without giving me the answer then that would be fantastic.

Best,

A

#### chisigma

##### Well-known member
Hi everyone,

I am new to the site so please let me know if I'm posting in the wrong place.

I am starting to teach myself number theory and would like a bit of help with a problem.

How would I go about showing "If m^2 = 0 (mod 3) then m = 0 (mod 3)"? I am then asked to deduce that root 3 is irrational.

If you could point me in the right direction without giving me the answer then that would be fantastic.

Best,

A
Wellcome on MHB Economan!... the congruence equation $\displaystyle m^{2} \equiv 0\ \text{mod}\ 3$ has the only solution $m \equiv 0\ \text{mod}\ 3$ because if $\displaystyle m^{2} \equiv 0\ \text{mod}\ 3$, then it exists an integer n for which is $\displaystyle m^{2}= 3\ n$ and that means that $\displaystyle m= \sqrt{3}\ \sqrt{n}$, which is true only if n is 0 or a multiple of 3...

Kind regards

$\chi$ $\sigma$

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hi everyone,

I am new to the site so please let me know if I'm posting in the wrong place.

I am starting to teach myself number theory and would like a bit of help with a problem.

How would I go about showing "If m^2 = 0 (mod 3) then m = 0 (mod 3)"? I am then asked to deduce that root 3 is irrational.

If you could point me in the right direction without giving me the answer then that would be fantastic.

Best,

A
Welcome to MHB, Economan!

I guess the key here, is to write it as an actual equation.
That is,
$$m^2 = 0 + 3k$$
for some integer k.

Since 3 is a factor on the right side, it must also be a factor on the left side.
How many factors 3 on the left side would that make?

#### Economan

##### New member
Thank you for your replies, chisigma and I like Serena.

I've followed what you said and get to here:

m^2 = 0 (mod 3) which implies that m^2 = 3k.

This leads to m = (root3)(rootk).

Can I then multiply by root3 to get (root3)m = 3(rootk), and does this then imply that either m or root3 are divisible by 3 - which means m is divisible by 3 as root3 is not?

I'm not sure if I can argue as above, so instead assumed that m^2 is a multiple of 3 but that m is not, i.e. that m = 3n +1 or 3n +2. I then squared each of these expressions and came to a contradiction. This seems a little cumbersome, so I hope there is a better way to do this.

Just to check, to prove irrationality of root3, I then let root3 = a/b, where a and b are the lowest integers possible, squared both sides to get 3b^2 = a^2 and used the result above to show that both a and b are divisible by 3 - contradicting my assumption that a and b are the lowest integers possible.

Thanks again for the input, and sorry if this is all pretty basic - I am just starting out with this and it is taking me a while to get used to proving things. It's really fun though!!

Best,

A

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Thank you for your replies, chisigma and I like Serena.

I've followed what you said and get to here:

m^2 = 0 (mod 3) which implies that m^2 = 3k.

This leads to m = (root3)(rootk).
Hold on. ;-)
In modulo arithmetic we only use integers - no roots.

The fact that the right side is divisible by 3, means the left side is also divisible by 3.
Since the left side is a product of integers, at least 1 of those integers has to be divisible by 3.
Specifically, m has to be divisible by 3, which completes the first part of your problem: $m \equiv 0 \pmod 3$.

Since m is divisible by 3, it also means that the left side (that is $m^2$) is divisible by $3^2$.
You need that for the part where you want to show that the square root of 3 is irrational (assume it is not...).

Just to check, to prove irrationality of root3, I then let root3 = a/b, where a and b are the lowest integers possible, squared both sides to get 3b^2 = a^2 and used the result above to show that both a and b are divisible by 3 - contradicting my assumption that a and b are the lowest integers possible.
That sounds right!

Last edited:

#### awkward

##### Member
Here is another approach which I like because it takes less thought. ("Thinking" is just another chance to make a mistake.) Just compute the values of $m^2 \pmod{3}$ for $m = 0, 1, 2$. We find the results are 0, 1, and 1, respectively. So we see that, for these three values (0, 1, 2), the only solution of $m^2 \equiv 0 \pmod{3}$ is 0.

Now, any integer is congruent to one of 0, 1, or 2 mod 3; and if $x \equiv y \pmod{3}$ then $x^2 \equiv y^2 \pmod{3}$. So if $m^2 \equiv 0 \pmod{3}$, we must have $m \equiv 0 \pmod{3}$.

Notice that with one simple computation, we found some additional information: the only possible values of $m^2 \pmod{3}$ are 0 and 1. This might come in handy in some other problem.

#### eddybob123

##### Active member
Just to check, to prove irrationality of root3, I then let root3 = a/b, where a and b are the lowest integers possible, squared both sides to get 3b^2 = a^2 and used the result above to show that both a and b are divisible by 3 - contradicting my assumption that a and b are the lowest integers possible.
This same proof structure is used to make the more general assertion that if the nth root of any positive integer is not an integer, then it is irrational.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Hi everyone,

I am new to the site so please let me know if I'm posting in the wrong place.

I am starting to teach myself number theory and would like a bit of help with a problem.

How would I go about showing "If m^2 = 0 (mod 3) then m = 0 (mod 3)"? I am then asked to deduce that root 3 is irrational.

If you could point me in the right direction without giving me the answer then that would be fantastic.

Best,

A
Here's a solution which is similar ot what awkward has posted.

Assume for a contradiction that $3$ doesn't divide $m$. Then,

Case 1: $m=3k+1$.
Here we have $m^2=3(3k^2+2k)+1$. Can you see the contradiction?

Case 2: $m=3k+2$.
Here we have $m^2=3(3k^2+4k+1)+1$. Can you see the contradiction?

In fact it is true in general that if a prime $p$ divies $m^k$ for some integers $m$ and $k$, then $p$ divides $m$ too. One way to show this is using the Euclidean algorithm.