• Support PF! Buy your school textbooks, materials and every day products Here!

More Proofs: Prove that if n is an odd positive int., then n^2 = 1(mod 8)

  • Thread starter VinnyCee
  • Start date
  • #1
489
0

Homework Statement



Prove that if n is an odd positive integer, then [itex]n^2\,\equiv\,1\,\left(mod\,8\right)[/itex].



Homework Equations



Theorem:

[tex]a\,\equiv\,b\left(mod\,m\right)[/tex]

if and only if

[tex]a\,mod\,m\,=\,b\,mod\,m[/tex]



The Attempt at a Solution



Using the theorem above:

[tex]a\,=\,n^2[/tex]

[tex]b\,=\,1,\,m\,=\,8[/tex]

Then I have this:

[tex]n^2\,mod\,8\,=\,1\,mod\,8[/tex]

What do I do next to show this for odd positive n?
 

Answers and Replies

  • #2
Päällikkö
Homework Helper
517
10
This is hardly "beyond calculus". Anyways, you can represent odd numbers with 2k + 1, where k is a natural number (or zero). Then use eg. proof by induction.
 
  • #3
dextercioby
Science Advisor
Homework Helper
Insights Author
12,980
540
You need to prove that [itex] (2k+1)^2=8p+1 [/itex] for some "k" and "p" in [itex] \mathbb{Z} [/itex].
 
  • #4
489
0
How would I go about proving that?

[tex]4\,k^2\,+\,4\,k\,+\,1\,=\,8\,p\,+\,1[/tex]

[tex]k^2\,+\,k\,=\,2\,p[/tex]

Now what?
 
  • #5
VietDao29
Homework Helper
1,423
1
If n is an odd number, then n can be expressed by (2k + 1) where k is any whole number. Right?
So, we have:
n2 = (2k + 1)2 = 4k2 + 4k + 1
= 4 (k2 + k) + 1 = 4k(k + 1) + 1
What can you say about the product of 2 successive integers? Hint: Is that divisible by 2?
So, is the product 4k(k + 1) divisible by 8?
Can you go from here? :)
 
  • #6
StatusX
Homework Helper
2,564
1
How would I go about proving that?

[tex]4\,k^2\,+\,4\,k\,+\,1\,=\,8\,p\,+\,1[/tex]

[tex]k^2\,+\,k\,=\,2\,p[/tex]

Now what?
p is any integer, so k^2+k=2p is equivalent to (ie, exactly the same question as) whether k^2+k is even. Well, is it?
 
  • #7
489
0
[itex]k^2\,+\,k[/itex] is always even. If k were odd, adding an odd integer to another odd one produces an even integer. If k were even, then the whole expression is even as well because adding two even integers always results in an even integer.
 

Related Threads for: More Proofs: Prove that if n is an odd positive int., then n^2 = 1(mod 8)

Replies
1
Views
2K
Replies
5
Views
7K
Replies
19
Views
6K
Replies
13
Views
2K
Replies
4
Views
2K
Replies
13
Views
17K
Replies
7
Views
2K
Replies
2
Views
8K
Top