Formal Modulus Proof: How close am I?

Printable View

October 12th 2008, 09:45 PM
aaronrj

Formal Modulus Proof: How close am I?

Show that if n is an odd positive integer then n^2 = 1(mod 8).

I see that any odd square has 1 as a remainder when calculated. Example: 49 = 7 * 7 = 1(mod 4), and any odd number squared equals an odd number. Let 2k represent all positive even integers. So n^2 = 1(mod 2k) for all odd positive integers.

Is this an acceptable proof?
October 12th 2008, 09:53 PM
Jhevon

Quote:

Originally Posted by aaronrj

Show that if n is an odd positive integer then n^2 = 1(mod 8).

I see that any odd square has 1 as a remainder when calculated. Example: 49 = 7 * 7 = 1(mod 4), and any odd number squared equals an odd number. Let 2k represent all positive even integers. So n^2 = 1(mod 2k) for all odd positive integers.

Is this an acceptable proof?

no, this proof is not acceptable. especially since you are trying to prove it with examples.

Assume $n$ is odd. then we can write $n = 2k + 1$ for some integer $k$ .

but that means $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$

now all you need to show is that you can write that expression in the form $8m + 1$ for some integer $m$ . since all numbers equivalent to 1 mod 8 have that form
October 13th 2008, 07:10 AM
aaronrj

need more help

Sorry, I see where you're going but I can't fill in the steps.

We have 4k^2 + 4k + 1

How does 8m + 1 fit into that?

Sub in 8m+1 for k?
October 13th 2008, 11:27 AM
Jhevon

Quote:

Originally Posted by aaronrj

Sorry, I see where you're going but I can't fill in the steps.

We have 4k^2 + 4k + 1

How does 8m + 1 fit into that?

Sub in 8m+1 for k?

no, here's a further hint: leave the +1 alone and factor an 8k out of the first two terms. you get

8k(k + 1)/2 + 1

now, obviously, your task is to find out whether k(k + 1)/2 is an integer
October 13th 2008, 07:41 PM
aaronrj

Correct Proof

Take 4k^2 + 4k + 1 = n^2
Factor: 4(k^2 + k) + 1 - 1 = n^2 - 1
Therefore: 4(k^2 + k) = n^2 - 1

This is how the book proves it.

I don't see where you were going with:

8k(k + 1)/2 + 1

Perhaps a bit more clarity is needed next time you attempt to offer aid.
October 13th 2008, 08:25 PM
Jhevon

Quote:

Originally Posted by aaronrj

Take 4k^2 + 4k + 1 = n^2
Factor: 4(k^2 + k) + 1 - 1 = n^2 - 1
Therefore: 4(k^2 + k) = n^2 - 1

This is how the book proves it.

I don't see where you were going with:

8k(k + 1)/2 + 1

Perhaps a bit more clarity is needed next time you attempt to offer aid.

that proof is not correct. look up the definition for $a \equiv b \mod n$ . you will see that it means $n \mid (a - b) \Longleftrightarrow a - b = nk$ for some $k \in \mathbb{Z}$ .

thus, saying $4(k^2 + k) = n^2 - 1$ is saying $n^2 \equiv 1\mod {\color{red}4}$ not $\mod 8$

to show that $n^2 \equiv 1\mod 8$ you must show that $8 \mid (n^2 - 1)$ , or in other words, $n^2 - 1 = 8k$ for some integer $k$ . that is what i was telling you to do. we need $8m = n^2 - 1$ for some integer $m$ , provided $n$ is odd.

we got to the point $n^2 - 1 = 8 \frac {k(k + 1)}2$

now, we complete the proof if we can show $\frac {k(k + 1)}2$ is an integer. that is what i leave it to you to do
October 14th 2008, 10:21 AM
aaronrj

Thanks.

Well, I guess I need to double check all of the proofs given in the book. Perhaps the author got lazy when writing the solutions. Thanks for clarifying the proof.
October 14th 2008, 10:27 AM
Jhevon

Quote:

Originally Posted by aaronrj

Well, I guess I need to double check all of the proofs given in the book. Perhaps the author got lazy when writing the solutions. Thanks for clarifying the proof.

well, we're not done. how would you finish up? is that expression an integer or not?
October 14th 2008, 12:05 PM
aaronrj

Did you not answer your own question?

Doesn't the theorem explicitly state that the expression must be an integer?

Theorem:
Let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km.

I definately should have referred to the definition first before trying to solve the problem; I would have had a much easier time. Lesson learned.
October 14th 2008, 04:15 PM
Jhevon

Quote:

Originally Posted by aaronrj

Doesn't the theorem explicitly state that the expression must be an integer?

Theorem:
Let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km.

I definately should have referred to the definition first before trying to solve the problem; I would have had a much easier time. Lesson learned.

we are to prove that it is an integer. assuming it is is begging the question. of course, if they ask you to prove something, they already know it is true. you are required to show why.
October 14th 2008, 04:54 PM
aaronrj

Predicate calculus

Let p represent the statement "The integers a and b are congruent modulo m."

Let q represent the statement "there is an integer k such that a = b + km."

If p $\Longleftrightarrow$ q

The domain is the set of all integers Z.

I don't think this is what you are looking for, but I thought I'd at least give it a shot.
October 14th 2008, 05:07 PM
Jhevon

Quote:

Originally Posted by aaronrj

Let p represent the statement "The integers a and b are congruent modulo m."

Let q represent the statement "there is an integer k such that a = b + km."

If p $\Longleftrightarrow$ q

The domain is the set of all integers Z.

I don't think this is what you are looking for, but I thought I'd at least give it a shot.

aaronrj, pay attention. i left off exactly where you should pick up. i did everything for you except the last step. all i want you to tell me, is whether k(k + 1)/2 is an integer or not (and why). that is all. do that and you are done. stop beating around the bush. i told you these definitions already, what point is there bringing them up?