Results 1 to 9 of 9

Math Help - congruence modulo m

  1. #1
    Member
    Joined
    Mar 2006
    Posts
    82

    congruence modulo m

    Hello, can anyone help me with these two problems?? Thank you so much in advance.


    1) Prove: If x ≡ y (mod m), then (x, m) = (y, m)



    2) Show that if n > 4 is not prime, then (n-1)! ≡ 0 (mod n).
    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 jenjen View Post
    Hello, can anyone help me with these two problems?? Thank you so much in advance.


    1) Prove: If x ≡ y (mod m), then (x, m) = (y, m)
    Let x,y,m>0.

    I presume it means \gcd (x,m)=\gcd (y,m).

    We know that,
    m|(x-y) thus, x-y=km for some k.

    Let \gcd(x,m)=d_1.
    Let \gcd(y,m)=d_2.
    We will prove it by trichtonomy.

    Assume d_1>d_2.
    But that cannot be because,
    y=x-km
    And d_1|x and d_1|km.
    Thus, d_1|(x-km) thus d_1|y. And we also know that d_1|m.
    Thus, \gcd(y,m)\not = d_2 because d_2<d_1. And hence it is not "greatest".

    By similar reasoning. We can show d_1<d_2 leads to contradiction.

    Thus, by trichtonomy,
    d_1=d_2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jenjen View Post
    2) Show that if n > 4 is not prime, then (n-1)! ≡ 0 (mod n).
    There are two possibilities.

    1)n is not a square.

    2)n is a square.

    If n is not a square then it has a non-trivial proper factorization n=ab where 2\leq a,b \leq n-1.
    Where a,b are distinct.
    Thus among the factors of (n-1)!:
    1,2,3....,n-1
    We can find its factors a,b.

    When n is a square there are 2 possibilities.
    1)n is not a square of a prime.
    2)n is a square of a prime.

    If n is not a square of a prime we know that n=c^2=cc=cab where 2\leq a,b\leq c-1 because it is not a prime. Thus, it has a factorization in the form n=ab where a,b are distinct and the same argument applies.

    If n is a square of a prime then we have a minor problem. For example if n=4=2^2 it does not work. Which is why the initial conditions of the problem says n>4. Thus we know that n=p^2 and in no other way. We know that 1,2,...,p,...n-1 contains one factor. But what about other another factor of p? It turns out that when n>4 the factor 2p appears among 1,2,...,n-1. Thus, there is another number that has a factor of p. The reason why is because p=\sqrt{n}\leq (n-1)/2 for n>4thus, 2p\leq n-1 and is hence among one of the factors.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2006
    Posts
    82
    thanks theperfecthacker for the quick reply!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    There are two possibilities.

    1)n is not a square.

    2)n is a square.

    If n is not a square then it has a non-trivial proper factorization n=ab where 2\leq a,b \leq n-1.
    Where a,b are distinct.
    Thus among the factors of (n-1)!:
    1,2,3....,n-1
    We can find its factors a,b.

    When n is a square there are 2 possibilities.
    1)n is not a square of a prime.
    2)n is a square of a prime.

    If n is not a square of a prime we know that n=c^2=cc=cab where 2\leq a,b\leq c-1 because it is not a prime. Thus, it has a factorization in the form n=ab where a,b are distinct and the same argument applies.

    If n is a square of a prime then we have a minor problem. For example if n=4=2^2 it does not work. Which is why the initial conditions of the problem says n>4. Thus we know that n=p^2 and in no other way. We know that 1,2,...,p,...n-1 contains one factor. But what about other another factor of p? It turns out that when n>4 the factor 2p appears among 1,2,...,n-1. Thus, there is another number that has a factor of p. The reason why is because p=\sqrt{n}\leq (n-1)/2 for n>4thus, 2p\leq n-1 and is hence among one of the factors.
    Hmm, you have:

    2 <= a,b <= n - 1, shouldn't it be: 1 < a < b < n - 1? Maybe you got it mixed up for when it is a square. The proof I was given was:

    Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.

    Does this work? It contradicts a few of your results.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post

    Hmm, you have:

    2 <= a,b <= n - 1, shouldn't it be: 1 < a < b < n - 1? Maybe you got it mixed up for when it is a square. The proof I was given was:

    Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.

    Does this work? It contradicts a few of your results.
    No. I said proper nontrivial factorization. Meaning the obvious factors, 1 and the number itself are excluded.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    No. I said proper nontrivial factorization. Meaning the obvious factors, 1 and the number itself are excluded.
    Sorry to be a pain, but I clearly understand your proof now TPF. What I don't understand is how the proof I was given (below) proves the claim; how does that tie it all together showing that n is composite if n > 4 and that n will then divide (n - 1)!

    Proof:

    Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Sorry to be a pain, but I clearly understand your proof now TPF. What I don't understand is how the proof I was given (below) proves the claim; how does that tie it all together showing that n is composite if n > 4 and that n will then divide (n - 1)!

    Proof:

    Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.
    How do you know that 2a<=n-1?
    And hence among the factors.
    See I acutally used an inequality to justify that.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    How do you know that 2a<=n-1?
    And hence among the factors.
    See I acutally used an inequality to justify that.
    I don't, my professor got that as a proof. But thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Modulo and congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 26th 2010, 05:10 PM
  2. congruence modulo twenty four
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 22nd 2010, 03:45 AM
  3. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 06:47 PM
  4. congruence property modulo p^2
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 13th 2009, 08:50 AM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 07:59 PM

Search Tags


/mathhelpforum @mathhelpforum