help: modular arithmetic

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 [tex]\sqrt n[/tex] is irrational if n is not a perfect square. i assumed that it is rational and
[tex]\sqrt n[/tex] = [tex]{a}\over{b}[/tex] where gcd(a,b) = 1.
then [tex]a^2 = nb^2[/tex]

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

[tex]nk^2 = b^2[/tex]

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² doesnt 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 [tex]\sqrt n[/tex] is irrational if n is not a perfect square?

Data

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

This can be reduced to the same thing. You can decompose any positive integer [itex]n[/itex] 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

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

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.