Formal Modulus Proof: How close am I?

• Oct 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?
• Oct 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
• Oct 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?
• Oct 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
• Oct 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.
• Oct 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
• Oct 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.
• Oct 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?
• Oct 14th 2008, 12:05 PM
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.
• Oct 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.
• Oct 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.
• Oct 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?