Results 1 to 3 of 3

Math Help - Proving Congruency

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    14

    Proving Congruency

    Prove that if n is an odd positive integer, then n^2 ≡ 1 (mod 8)


    also


    Show that if n|m, where n and m are positive integers greater than 1, and if a ≡ b (mod m), where a and b are integers, then a ≡ b (mod n)



    Just started doing congruencies. I understand mod no problem, but I am really lost when it comes to congruencies. Any help would be great.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Eclyps19 View Post
    Prove that if n is an odd positive integer, then n^2 ≡ 1 (mod 8)
    You need to show 8 divides (n^2 - 1) meaning 8 divides (n+1)(n-1)

    If n is odd then n = 2k+1 so (n+1) = 2(k+1) and n-1 = 2k. That means (n+1)(n-1) = 4k(k+1) now one of k or k+1 is even by pigeonhole and so this is divisible by 8.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    629
    Hello, Eclyps19!

    Show that if n|m, where n\text{ and }m are positive integers greater than 1,

    and if a \equiv b\;(\text{mod }m), where a\text{ and }b are integers, then: . a \:\equiv\:b\;(\text{mod }n)

    Definition: . a \:\equiv\:b\;(\text{mod }n) \quad\Longleftrightarrow\quad a - b \:=\:kn

    "a\text{ is congruent to }b\text{, mod }n\text{" means: "the difference of }a\text{ and }b\text{ is a multiple of }n."


    We are told that: n\text{ divides }m\text{, hence: }m = hn\text{ for some integer }h.

    We are given: . a\:\equiv\;b\;(\text{mod }m)\quad\Rightarrow\quad a - b \:=\:km

    Since m = hn\text{, we have: }\;a - b \:=\:k(hn) \:=\:(kh)n

    Hence: . a - b\text{ is a multiple of }n.


    . . Therefore: . a \:\equiv\:b\;(\text{mod } n)

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: November 21st 2010, 12:16 PM
  2. Help with congruency
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: October 20th 2009, 02:41 AM
  3. Congruency
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 7th 2009, 01:14 PM
  4. Replies: 1
    Last Post: September 14th 2008, 12:25 PM
  5. Need help with CONGRUENCY!!! @__@?
    Posted in the Geometry Forum
    Replies: 2
    Last Post: November 29th 2007, 11:59 PM

Search Tags


/mathhelpforum @mathhelpforum