Mastering Modular Arithmetic: Proving a2 ≡ 0 (mod n) with Expert Tips

[murshid_islam]

hi,

i have started "self-studying" number theory. and since i am quite new to number theory and modular arithmetic, i need some help.
how can i prove that if a² ≡ 0 (mod n), then a ≡ 0 (mod n).

thanks in advance to anybody who can help.

 

[matt grime]

You can't, because it is false. Find a simple counter example.

 

[murshid_islam]

well, i was trying to prove that \sqrt n is irrational if n is not a perfect square. i assumed that it is rational and
\sqrt n = {a}\over{b} where gcd(a,b) = 1.
then a^2 = nb^2

now n divides a². if only i could prove that n divides a, then i could put a = nk and get
n^2k^2 = nb^2

nk^2 = b^2

and now n divides b². now if n divides b then n divides both a and b. thus gcd(a,b) is not 1 as it was assumed.

but how can i prove it? since n divides a² doesn't imply n divides a.

 

[matt grime]

Just think about the prime decompostion of n. It suffices to assume that n is square free (i.e. no prime divides n more than once).

 

[murshid_islam]

so if a prime divides n once and n divides a², then that prime divides a² twice. hence that prime divides a once. is that it?

 

[matt grime]

No. That is not it. It is true that if p divides a^2 that p^2 divides a^2, but it if you assume that you are assuming the result. You want to prove that fact.

 

[murshid_islam]

could you please elaborate?

 

[matt grime]

How have you decided p^2 divides a^2? You have either got a circular argument or an unnecessary step.

The definition of prime is p is prime if p|ab implies p|a or p|b, by the way. (You should prove this is equivalent to your definition if yours is different.)

 

[murshid_islam]

ok, then can you please help me with the proof that \sqrt n is irrational if n is not a perfect square?

 

[Data]

Are with you familiar with the usual argument for why, say, \sqrt{p} is irrational when p is prime?

This can be reduced to the same thing. You can decompose any positive integer n into the product of a squarefree integer and a perfect square (note that 1 is a squarefree integer AND a perfect square), which is what matt meant by "it is sufficient to assume n is squarefree." Try to use that to prove it.

 

[matt grime]

Your line of argument is perfectly fine as long as you take care with it. There are all manner of fussy ways of writing it, but it suffices to assume that n is square free (and not equal to 1). Then if n=a^2/b^2, and p is a prime that divides n we reach an obvious contradiction along the lines you've discussed.

 

[murshid_islam]

ok tell me if this is right:
if a prime p divides a², then p² also divides a². and since p² divides a², i.e., p.p divides a.a, then p divides a. am i correct?

 

[matt grime]

How are you concluding that p^2 divides a^2 if p divides a^2? I only ask, again, because the usual way of proving this fact is to prove that p divides a by the definition of primeness. So as I am now saying for the third time you are either using a circular argument or you're doing something unnecessary.The fact that 'if divides a^2 then p divides a' is an immediate consequence of the (proper) definition of prime, as I have, again, already told you.

The result is not true for non-primes, and at no point do you explain why p being prime is important, so no, this is not sufficient proof, in my opinion.

 

[murshid_islam]

How are you concluding that p^2 divides a^2 if p divides a^2?

suppose the prime decomposition of a = p₁.p₂...p_n.
then a² = p₁².p₂²...p_n².

now, if p_k divides a², then p_k² also divides a².

and if p_k² divides a², i.e., if p_k.p_k divides a.a, then p_k divides a.

 

[matt grime]

You are assuming that prime factorization is unique, then, but not bothering to say so. That is bad: your proof is flawed.

If p divides ab then p divides a or b is the definition of prime so use to, for pity's sake.

 

[murshid_islam]

You are assuming that prime factorization is unique, then

isn't that the fundamental theorem of arithmetic? i am not assuming it. i know that it is true.

 

[matt grime]

Ok, I'm going to give up flogging this dead horse and leave you with a repeat of what I've been saying all along: your argument is too long and relies on unstated results, and now that you have stated them we see it is circular. If you're going to use the fundamental theorem of arithmetic say you're using it. The fact that p divides a if p divides a^2 is a consequence of the definition of primeness. You do not need to invoke uniqueness of prime factorization to deduce it, and in fact this is circular logic beause the proof the the fundamental theorem of arithmetic is a consequence of a special case of the very result you're using the fundamental theorem of arithmetic to prove.

 

[murshid_islam]

in fact this is circular logic beause the proof the the fundamental theorem of arithmetic is a consequence of a special case of the very result you're using the fundamental theorem of arithmetic to prove.

thank you very much for this info. i couldn't understand before why you were saying "circular logic". now i see that my reasoning was indeed "circular". thanks once again.