# Thread: Proof Help

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

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

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

5. Thank you both Dinkydoe Drexel28.

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

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

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

10. Thank you for your help.