Results 1 to 10 of 10

Math Help - Proof Help

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    35

    Proof Help

    Hi

    Can someone please solve this problem:

    Proof Help-untitled.jpg


    I know Fermat’s Little Theorem states that:

    Let p be a prime number. If a is any integer not divisible by p, then:


    Proof Help-a257bad1e90b56abcc9ab047b1911b6f.png

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by SubZero View Post
    Hi

    Can someone please solve this problem:

    Click image for larger version. 

Name:	Untitled.jpg 
Views:	40 
Size:	36.3 KB 
ID:	14797


    I know Fermat’s Little Theorem states that:

    Let p be a prime number. If a is any integer not divisible by p, then:


    Click image for larger version. 

Name:	a257bad1e90b56abcc9ab047b1911b6f.png 
Views:	89 
Size:	719 Bytes 
ID:	14798

    Thanks
    The first one you need merely prove that p\ne 2,5\implies (10,p)=1 so that Fermat's applies. The second one would be nice if this was group theory! Otherwise, note that by the division algorithm we have that k=m(p-1)+r for some 0\leqslant r< p-1. So 1\equiv 10^k=10^{m(p-1)}10^r\equiv 10^r\text{ mod }p and since 10^{r}\equiv 1\text{ mod }p with 0\leqslant r< p-1 only if r=0 we may conclude that k=m(p-1). The last one is up to you, son.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    To be more precise: the theorem states for any a coprime with p we have:

    a^{p-1}\equiv 1 mod p

    Observe :gcd(10, p) = 1 , 10 and p are coprime since 2,5\neq p

    (b) It's known that (\mathbb{Z}/p\mathbb{Z})^* is a cyclic group of order p-1. Thus if k is the smallest number such that 10^k = 1 mod p then ord _p(10) = k. Hence k|p-1 in the group (\mathbb{Z}/p\mathbb{Z})^*

    (c) is a consequence of long division.

    (ehr..sorry drex. my post has just become useless ;p)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Dinkydoe View Post
    To be more precise: the theorem states for any a coprime with p we have:

    a^{p-1}\equiv 1 mod p

    Observe :gcd(10, p) = 1 , 10 and p are coprime since 2,5\neq p

    (b) It's known that (\mathbb{Z}/p\mathbb{Z})^* is a cyclic group of order p-1. Thus if k is the smallest number such that 10^k = 1 mod p then ord _p(10) = k. Hence k|p-1 in the group (\mathbb{Z}/p\mathbb{Z})^*

    (c) is a consequence of long division.

    (ehr..sorry drex. my post has just become useless ;p)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    35
    Thank you both Dinkydoe Drexel28.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2009
    Posts
    35
    Quote Originally Posted by Dinkydoe View Post
    To be more precise: the theorem states for any a coprime with p we have:

    a^{p-1}\equiv 1 mod p

    Observe :gcd(10, p) = 1 , 10 and p are coprime since 2,5\neq p

    (b) It's known that (\mathbb{Z}/p\mathbb{Z})^* is a cyclic group of order p-1. Thus if k is the smallest number such that 10^k = 1 mod p then ord _p(10) = k. Hence k|p-1 in the group (\mathbb{Z}/p\mathbb{Z})^*

    (c) is a consequence of long division.

    (ehr..sorry drex. my post has just become useless ;p)


    How can we do Part (c) from long division. I really do not understand .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by SubZero View Post
    How can we do Part (c) from long division. I really do not understand .
    How do we represent an infinite decimal expansion?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Let 1/p = 0,q_1q_2,q_3,\cdots q_k, q_{k+1}\cdots

    We have 10^k\equiv 1 mod p

    10/p = q_1p+r_1
    10r_1 = q_2p + r_2
    10r_2= q_3p+ r_3
    etc.

    That is how we apply the long division algorithm:

    Observe:
    10\equiv r_1 mod p
    10r_1\equiv 10^2\equiv r_2 mod p
    10r_2\equiv 10^3 \equiv r_3 mod p

    \cdots

    \cdots

    10r_{k-1}\equiv 10^k\equiv  1 mod p
    10r_k\equiv 10^{k+1}\equiv 10\equiv r_1 mod p

    From this follows that q_1 = q_{k+1}
    (and the cycle repeats again)

    Guess we still have to prove there's no sub-period d|k
    Last edited by Dinkydoe; January 14th 2010 at 02:42 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Hm. Well for the decimal expansion of 1/p= 0,q_1,\cdots q_k,q_{k+1}, where k= p-1 we have that q_{k+1}= q_{1} But it may still be we have a shorter cycle:

    For example 1/11 = 0,0909090909... It's still true that q_{10}= q_{1} and in general q_{n}= q_{n+k}

    But It's also true we have: q_n= q_{n+2} in this case.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Nov 2009
    Posts
    35
    Thank you for your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum