Results 1 to 10 of 10

Thread: 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
    22
    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 $\displaystyle 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 $\displaystyle k=m(p-1)+r$ for some $\displaystyle 0\leqslant r< p-1$. So $\displaystyle 1\equiv 10^k=10^{m(p-1)}10^r\equiv 10^r\text{ mod }p$ and since $\displaystyle 10^{r}\equiv 1\text{ mod }p$ with $\displaystyle 0\leqslant r< p-1$ only if $\displaystyle r=0$ we may conclude that $\displaystyle 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 $\displaystyle a$ coprime with p we have:

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

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

    (b) It's known that $\displaystyle (\mathbb{Z}/p\mathbb{Z})^*$ is a cyclic group of order p-1. Thus if k is the smallest number such that $\displaystyle 10^k = 1$ mod p then ord$\displaystyle _p(10) = k$. Hence k|p-1 in the group $\displaystyle (\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
    22
    Quote Originally Posted by Dinkydoe View Post
    To be more precise: the theorem states for any $\displaystyle a$ coprime with p we have:

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

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

    (b) It's known that $\displaystyle (\mathbb{Z}/p\mathbb{Z})^*$ is a cyclic group of order p-1. Thus if k is the smallest number such that $\displaystyle 10^k = 1$ mod p then ord$\displaystyle _p(10) = k$. Hence k|p-1 in the group $\displaystyle (\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 $\displaystyle a$ coprime with p we have:

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

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

    (b) It's known that $\displaystyle (\mathbb{Z}/p\mathbb{Z})^*$ is a cyclic group of order p-1. Thus if k is the smallest number such that $\displaystyle 10^k = 1$ mod p then ord$\displaystyle _p(10) = k$. Hence k|p-1 in the group $\displaystyle (\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
    22
    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 $\displaystyle 1/p = 0,q_1q_2,q_3,\cdots q_k, q_{k+1}\cdots$

    We have $\displaystyle 10^k\equiv 1$ mod p

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

    That is how we apply the long division algorithm:

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

    $\displaystyle \cdots$

    $\displaystyle \cdots $

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

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

    Guess we still have to prove there's no sub-period $\displaystyle d|k$
    Last edited by Dinkydoe; Jan 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 $\displaystyle 1/p= 0,q_1,\cdots q_k,q_{k+1}$, where $\displaystyle k= p-1$ we have that $\displaystyle 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 $\displaystyle q_{10}= q_{1}$ and in general $\displaystyle q_{n}= q_{n+k}$

    But It's also true we have: $\displaystyle 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: Jun 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 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: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum