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
    10
    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
    10
    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
    10
    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
    10
    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, 06:10 PM
  2. congruence modulo twenty four
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 22nd 2010, 04:45 AM
  3. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 07:47 PM
  4. congruence property modulo p^2
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 13th 2009, 09:50 AM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 08:59 PM

Search Tags


/mathhelpforum @mathhelpforum