Welcome to our community

Be a part of something great, join today!

Number Theory Modular arithmetic problem

Economan

New member
Jul 17, 2013
2
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
Feb 13, 2012
1,704
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
Mar 5, 2012
8,780
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
Jul 17, 2013
2
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
Mar 5, 2012
8,780
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
Feb 18, 2012
36
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
Aug 18, 2013
76
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
Mar 10, 2012
834
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.