1. ## Proof Help

Hi

Can someone please solve this problem:

I know Fermat’s Little Theorem states that:

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

Thanks

2. Originally Posted by SubZero
Hi

Can someone please solve this problem:

I know Fermat’s Little Theorem states that:

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

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.

3. 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)

4. Originally Posted by Dinkydoe
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)

5. Thank you both Dinkydoe Drexel28.

6. Originally Posted by Dinkydoe
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 .

7. Originally Posted by SubZero
How can we do Part (c) from long division. I really do not understand .
How do we represent an infinite decimal expansion?

8. 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$

9. 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.

10. Thank you for your help.