Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - [SOLVED] two questions I am stumped on

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    42

    [SOLVED] two questions I am stumped on

    Hi, first post here though I have been using the search feature to help myself through an onlin Intro to Number Theory class. I am stumped on two congruence questions.

    1. If n>4 is a composite number, show that n|(n-1)! Conclude that (n-1)! not congruent -1(mod n).

    (This shows that Wilson's theorem can be used as a proof of primality. It is unfortunately not practical for large numbers)

    2. Use the congruence equation x^2 - 1 congruent 0(mod p) to show that if (a,p) = 1, then a^((p-1)/2) congruent +/- 1(mod p).


    I in words why a composite (ab) number does not work, but am not really sure how to prove it. And for the second one, I do not really know how to start. Any help would be greatly appreciated as searching did not turn up anything really helpful to me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hi,
    Quote Originally Posted by Proggy View Post
    Hi, first post here though I have been using the search feature to help myself through an onlin Intro to Number Theory class. I am stumped on two congruence questions.

    1. If n>4 is a composite number, show that n|(n-1)! Conclude that (n-1)! not congruent -1(mod n).

    (This shows that Wilson's theorem can be used as a proof of primality. It is unfortunately not practical for large numbers)

    2. Use the congruence equation x^2 - 1 congruent 0(mod p) to show that if (a,p) = 1, then a^((p-1)/2) congruent +/- 1(mod p).


    I in words why a composite (ab) number does not work, but am not really sure how to prove it. And for the second one, I do not really know how to start. Any help would be greatly appreciated as searching did not turn up anything really helpful to me.
    I have little time... but I'll try.

    For the first one, consider that (n-1)! contains any integer inferior or equal to n-1 as a factor, that is to say any integer inferior to n. Now, if n is a composite number, then it's the product of at least 2 integers that are inferior to n. But these 2 numbers are in the product (n-1)!. Thus you can retrieve n in (n-1)! --> n divides (n-1)!
    I hope it's clear enough... !
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by Moo View Post
    Hi,

    I have little time... but I'll try.

    For the first one, consider that (n-1)! contains any integer inferior or equal to n-1 as a factor, that is to say any integer inferior to n. Now, if n is a composite number, then it's the product of at least 2 integers that are inferior to n. But these 2 numbers are in the product (n-1)!. Thus you can retrieve n in (n-1)! --> n divides (n-1)!
    I hope it's clear enough... !
    So since a|(n-1)! and b|(n-1)!, then ab|(n-1)!. That helps, I can flesh it out from there. One thing I wonder though, it seems to me that this method might be thrown off if a=b?

    And no worries on the time, I appreciate any help. I am on lesson 12 of 16 lessons in the course. I have struggled through up to this point, but some of these problems are leaving me not even knowing where to start. The book states a theorem and the proof, but it leaves a lot to the imagination as it does not give much in the way of actual examples of using the theorems to solve problems. I do not mean to look like I am not trying. I find that one of two things happens with my homework. Most of the time I figure out a starting point and manage my way to a solution. But I am finding a few problems where I just do not know how to start and those make it look like I am not trying.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    You can read this.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by ThePerfectHacker View Post
    You can read this.
    Thanks TPH, I had done a search on congruence and with all the threads to read I had skipped that one due to the title referring to the first of the two problems in the thread. That definitely answered my question of when a=b, or n=a^2.

    Though it is obviously true from your proof, I would not have known immediately that...
    Quote Originally Posted by ThePerfectHacker View Post
    The reason why is because for thus, and is hence among one of the factors.
    I would very much appreciate any hints on how to begin the second problem. Will spend some more time tomorrow clicking every searched thread containing congruence.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    #2 is known as Euler's criterion .. or at least it's part of it anyway.

    Let g be a primitive root of p. Then, a \equiv g^{k} \: (\text{mod } p) for some k since a is a least residue mod p and all the powers of g from 1 to \phi(p) = p -1 are a permutation of all least residues relatively prime to p (which is what we have since (a, p) = 1.

    If k is even, then a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{k/2})^{(p-1)} \equiv 1 \: (\text{mod } p) by Fermat's theorem.

    If k is odd, then a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{(p-1)/2})^{k} \equiv (-1)^{k} \equiv -1 \: ( \text{mod } p)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by o_O View Post
    #2 is known as Euler's criterion .. or at least it's part of it anyway.

    Let g be a primitive root of p. Then, a \equiv g^{k} \: (\text{mod } p) for some k since a is a least residue mod p and all the powers of g from 1 to \phi(p) = p -1 are a permutation of all least residues relatively prime to p (which is what we have since (a, p) = 1.

    If k is even, then a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{k/2})^{(p-1)} \equiv 1 \: (\text{mod } p) by Fermat's theorem.

    If k is odd, then a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{(p-1)/2})^{k} \equiv (-1)^{k} \equiv -1 \: ( \text{mod } p)
    Can that be done without the use of primitive roots? This is a problem from section 3.6 in the book and section 3.7 is titled Primitive Roots, so the book is not expecting me to know about those yet.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    how about the Legendre's Number? are you allowed to use it?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by kalagota View Post
    how about the Legendre's Number? are you allowed to use it?
    I did not recognize the name, so I checked the index and Legendre only shows up once, on page 2 no less, concerning his thoughts that helped lead to the prime number theorem. So I guess no, I can not use it.

    The section I am doing this problem from is named Polynomial Congruences. It includes distinct solutions to congruent polynomials, a couple unnamed theorems that I can not seem to apply to this problem and Wilson's Theorem.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Proggy View Post
    Use the congruence equation x^2 - 1 congruent 0(mod p) to show that if (a,p) = 1, then a^((p-1)/2) congruent +/- 1(mod p).
    If \gcd(a,p)=1 then a^{p-1}\equiv 1(\bmod p).
    Thus, a^{p-1} - 1\equiv 0 (\bmod p).
    Thus, (a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 (\bmod p) ---> if p\not = 2.
    Thus, a^{(p-1)/2} \equiv \pm 1(\bmod p).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by ThePerfectHacker View Post
    If \gcd(a,p)=1 then a^{p-1}\equiv 1(\bmod p).
    Thus, a^{p-1} - 1\equiv 0 (\bmod p).
    Thus, (a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 (\bmod p) ---> if p\not = 2.
    Thus, a^{(p-1)/2} \equiv \pm 1(\bmod p).

    Wouldn't the first line be dependent on p being prime? That is one of the requirements of Fermat's Theorem? Other than being confused on the first assumption, I followed the rest of it easy enough. And that confusion is what prevented me from starting out that way in the first place. I am obviously just missing something easy?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by Proggy View Post
    Wouldn't the first line be dependent on p being prime? That is one of the requirements of Fermat's Theorem? Other than being confused on the first assumption, I followed the rest of it easy enough. And that confusion is what prevented me from starting out that way in the first place. I am obviously just missing something easy?
    in fact, that line is the fermat's little theorem itself..
    haven't you proved that yet?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by kalagota View Post
    in fact, that line is the fermat's little theorem itself..
    haven't you proved that yet?
    yes, but in the book, the theorem starts with "Suppose p is a prime. Then for all a"...then the formula. The p-1 is based on the number of integers in a reduced residue system, which for prime p is p-1, but if p is not prime, then it would not be p-1. That is the way my intro book explains it and that is why that first line confuses me.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    well, if p were not prime, then it would be useless to talk about the formula.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    okay, I just realized what I might have not have been taking as an assumption before. In Number Theory, if they use p to represent a number in a theory, is it to be assumed that p is prime even without explicitly stating it, such as in the problem I posted in the original post? I was assuming that when talking about a prime number, you used p to represent it. BUt I had not been assuming that all p's would then imply a prime number. It makes sense, but if I have learned anything in this class, it has been to not take anything for granted.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: October 14th 2010, 04:59 AM
  2. Stumped on two questions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: September 30th 2009, 06:50 AM
  3. [SOLVED] Stumped - Help get me started
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2009, 05:47 PM
  4. [SOLVED] Stumped on this DE
    Posted in the Calculus Forum
    Replies: 8
    Last Post: March 14th 2009, 12:37 PM
  5. Two calc questions...stumped
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 30th 2008, 03:22 PM

Search Tags


/mathhelpforum @mathhelpforum