Proofs involving congruence.

[Max.Maxim]

Let n∈Z. Prove the statement
If n≡4 mod 9, then n^2≡7 mod 9
So what I did was:
Proof: Assume that n≡4(mod9). Then 9|n and so n= 9q for some integer. Since n^2=81q^2=7(7q^2) is an integer, n^2 ≡7 mod 9
So could this possibly work?

 

[Dr.Peterson]

Let n∈Z. Prove the statement
If n≡4 mod 9, then n^2≡7 mod 9
So what I did was:
Proof: Assume that n≡4(mod9). Then 9|n and so n= 9q for some integer. Since n^2=81q^2=7(7q^2) is an integer, n^2 ≡7 mod 9
So could this possibly work?

How do you conclude from n≡4(mod9) that 9|n ?

What should that be instead?

 

[Max.Maxim]

9|4n would make it work Dr. Peterson?

 

[Dr.Peterson]

9|4n would make it work Dr. Peterson?

No.

Before you propose an answer, ask yourself, how could I convince someone else that I am right?

And look up the definition of congruence, to refresh your memory.

 

[Steven G]

a | b if b = ka, for some k in Z.

a ≡ b mod(c). This means that when a is divided by c the remainder is b.

For example 27 ≡ 2 mod(25) because when you divide 27 by 25 the remainder is 2.

Mods are just remainders. You must get down the definition. Remember that you can't play the game if you don't know the rules. The definitions are the rules.

So what does n≡4 mod 9 mean? What does n^2≡7 mod 9? Is the statement that you want to prove correct?

 

[Max.Maxim]

I'm lost, so could you possibly pinpoint where exactly are messed up with this proof?

 

[Dr.Peterson]

Here is the definition I like, which is closer to what you started with than Jomo's:

a ≡ b (mod m) if and only if m | (a-b).​

It's not a, but a-b, that is divisible by m.

 

[Steven G]

I will do this one for you as it can be abstract but the rest of your problems you have to do on your own or with help from this forum.

n≡4 mod 9 means that when you divide n by 9 the remainder is 4. That is n = 9k + 4 for some integer k.

Then n^2 = (9k + 4)^2 = 81k^2 + 72k + 16 = 81k^2 + 72K + 9 + 7 = 9(9k^2 + 8k + 1) + 7 = 9m + 7

So n^2 = 9m + 7. That is when you divide n^2 by 9 the remainder is 7. This can be written in mod form as n^2 ≡ 7 mod(9)

Is this clear? Go over every line carefully.

For the record I hate modular arithmetic. I need to have the definition of a ≡ b (mod c) in front of me to do such problems. Now if I can it, I am sure that you can do it. All I did was use the definition.

 

[HallsofIvy]

Your basic problem is that you are trying to prove something about "congruence" without knowing what "congruent" means! The first thing you should do before attempting any mathematical proof is be clear on all the relevant definitions.

If n is congruent to 4 (mod 9) then n is NOT divisible by 9. Dividing n by 9 gives a remainder of 4. Specifically, n= 9k+ 4 for some integer k.

 

[Max.Maxim]

Okay, just so I'm on the correct route.
If n ≡ 1 mod 9, then n ≡ 1 mod 9. For example
Proof:
Assume that n≡1 mod 9, then n≡1 mod 9, that is 9k+1
Then n^2=(9k+1)^2=(81k^2+72k)+1=9(9k^2+8)+1=9q+1
So n^2=9q+1

 

[Steven G]

Why would you write If n ≡ 1 mod 9, then n ≡ 1 mod 9. It is true, but why write it. It really says nothing. And you wrote it twice. Then you wrote Proof. You did NOT state what you wanted to prove!

For the record, (9k+1)^2 is NOT 81k^2 + 72K + 1. Where did the 72k from from? Please try again.

You arrived at n^2 = 9q + 1. You failed to write this in mod form. You should say n^2= 9q+1 means A≡B mod C where you need to decide what A, B and C should be.

 

[HallsofIvy]

"If A then A" is a "tautology" for all A. You don't need to prove it!