Thread: 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?

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 is odd. then we can write for some integer .

but that means

now all you need to show is that you can write that expression in the form for some integer . since all numbers equivalent to 1 mod 8 have that form

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?

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

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.

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 . you will see that it means for some .

thus, saying is saying not

to show that you must show that , or in other words, for some integer . that is what i was telling you to do. we need for some integer , provided is odd.

we got to the point

now, we complete the proof if we can show is an integer. that is what i leave it to you to do

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.

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?

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.

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.

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 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.

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 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?