Results 1 to 4 of 4

Thread: really cant do

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    321

    really cant do

    Attached Thumbnails Attached Thumbnails really cant do-323.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie Klaus's Avatar
    Joined
    May 2008
    Posts
    10
    Hello,
    For question (a): Each number n in the sum is lower than p. So, (n,p)=1.
    Hence, we can apply Fermat's Little Theorem:
    $\displaystyle n^{p-1}\equiv 1\text{ mod }p$
    Let's multiply both sides by n.
    $\displaystyle n^{p}\equiv n\text{ mod }p$
    Thus
    $\displaystyle \sum_{n=1}^{p-1} n^p\equiv \sum_{n=1}^{p-1} n\equiv \frac{(p-1)(p)}{2}\text{ mod }p$
    Isn't it ?
    Last edited by Klaus; Jun 23rd 2008 at 06:57 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    For (a) we can strengthen the problem. $\displaystyle 1^k + 2^k + ... + (p-1)^k \equiv 0 (\bmod p)$ if $\displaystyle (p-1)\not | k$ and $\displaystyle \equiv p$ if $\displaystyle (p-1)| k$.

    For (b) note $\displaystyle 1+...+p = p\cdot \frac{p-1}{2}$. Let $\displaystyle a=\frac{p-1}{2}$.
    Let $\displaystyle r$ be remainder of $\displaystyle (p-1)!$ mod $\displaystyle pa$.
    Thus, $\displaystyle (p-1)!\equiv r(\bmod pa)$ thus $\displaystyle (p-1)!\equiv r(\bmod p)$ and $\displaystyle (p-1)!\equiv r(\bmod a)$.

    By Wilson's theorem it follows that $\displaystyle r\equiv -1(\bmod p)$.
    Also $\displaystyle r\equiv 0(\bmod a)$ because $\displaystyle a$ divides $\displaystyle (p-1)!$.
    If we let $\displaystyle r=p-1$ it satisfies both conditions.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    For the second problem let $\displaystyle y$ be the order of $\displaystyle a$ mod $\displaystyle b$. Let $\displaystyle a^x\equiv 1(\bmod b)$. Write $\displaystyle x=qy+r$ where $\displaystyle 0\leq r < y$. Then, $\displaystyle a^x \equiv 1 (\bmod b)\implies a^{qy+r}\equiv 1(\bmod b)\implies a^r\equiv 1(\bmod b)$. Since $\displaystyle y$ is the order of $\displaystyle a$ it means $\displaystyle a^r\not \equiv 1$ if $\displaystyle 0<r<y$. But since $\displaystyle 0\leq r < y$ and $\displaystyle a^r\equiv 1(\bmod b)$ it follows that $\displaystyle r=0$. And thus $\displaystyle x=qy+r = qy\implies y|x$.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum