## help: modular arithmetic

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 a2 ≡ 0 (mod n), then a ≡ 0 (mod n).

thanks in advance to anybody who can help.
 Recognitions: Homework Help Science Advisor You can't, because it is false. Find a simple counter example.
 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 a2. 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 b2. 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 a2 doesnt imply n divides a.

Recognitions:
Homework Help

## help: modular arithmetic

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).
 so if a prime divides n once and n divides a2, then that prime divides a2 twice. hence that prime divides a once. is that it?
 Recognitions: Homework Help Science Advisor 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.
 Recognitions: Homework Help Science Advisor 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.)
 ok, then can you please help me with the proof that $$\sqrt n$$ is irrational if n is not a perfect square?
 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.
 Recognitions: Homework Help Science Advisor 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.
 ok tell me if this is right: if a prime p divides a2, then p2 also divides a2. and since p2 divides a2, i.e., p.p divides a.a, then p divides a. am i correct?
 Recognitions: Homework Help Science Advisor 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.

 Quote by matt grime How are you concluding that p^2 divides a^2 if p divides a^2?
suppose the prime decomposition of a = p1.p2....pn.
then a2 = p12.p22....pn2.

now, if pk divides a2, then pk2 also divides a2.

and if pk2 divides a2, i.e., if pk.pk divides a.a, then pk divides a.
 Recognitions: Homework Help Science Advisor 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.

 Quote by matt grime 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.
 Recognitions: Homework Help Science Advisor 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.