Results 1 to 2 of 2

Math Help - Need help proving a congruence statement

  1. #1
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    597

    Need help proving a congruence statement

    *Sorry if this isn't the correct section. I'm not too sure about the naming of topics and my course is simply called "Discrete Mathematics" and I got an infraction last time for posting in this thread that's why I'm saying.*

    Ok so the question is: "Is it true that for all natural numbers n, if ab ≡ ac (mod n), then b ≡ c (mod n). Justify your answer."

    My friend wrote something which I agree with quite a lot but do not fully understand everything.

    So, everything that is simply written is what I agree with while the stuff marked with "*[a number]" is stuff I still question or have trouble with.

    Hypothesis:
    ab ≡ ac (mod n) ∀n ∈ ℕ [*1]
    a ≡ a (mod n) [*2]

    Conclusion:
    b ≡ c (mod n)
    ab ≡ ac (mod n) ⇔ ab - ac = nq, q ∈ ℤ
    ab ≡ ac (mod n) ⇔ a(b-c) = nq

    a ≡ a (mod n) ⇔ a - a = ns, s ∈ ℤ [*3]
    a ≡ a (mod n) ⇔ a(1-1) = ns where s = 0 [*3]

    [1] a(b-c) = nq ⇒ b - c = n ⇒ b ≡ c (mod n))
    [2] a(b-c) = nq if a = 0 ⇒ TRUE

    I put [*1] because my teacher said that "that is not always true". Is he right? If so, can someone please elaborate? For [*2], how do we know that? For [*3], I don't see the relevance of that step in the grand scheme of things.

    Any help would be GREATLY appreciated!
    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    That is true only when gcd(a,n)=1.

    Try to prove this:

    If ab ≡ ac (mod n) then b ≡ c (mod n/d), when d=gcd(a,n)
    (The conclusion from here is my first line in this post).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving a statement is true.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 25th 2011, 01:13 AM
  2. Proving a statement by Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 20th 2011, 03:57 AM
  3. Replies: 1
    Last Post: October 18th 2010, 06:43 AM
  4. Help on proving this statement...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 20th 2008, 12:47 PM
  5. Proving Statement True
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 15th 2008, 01:38 AM

Search Tags


/mathhelpforum @mathhelpforum