2
$\begingroup$

I am having trouble proving Fermat's little theorem using group theory. These are my steps so far:

Let $(Z_p,+,\times)$ a Field, and we assume we know that the non-zero elements form a Group multiplicatively of order $p-1$, and we know that the order for all $a$ in the group $(Z_p,\times)$, is $x$ such that $a^x\equiv 1\pmod p$. We need to show that $x=p-1$. Well, the subgroup generated by $a$ of order $x$ must divide the order of the group $p-1$, so $x|p-1$ by Lagrange, and so $p-1=x*m$ for some $m$ positive integer. So $a^{p-1}=a^{x*m}=1^m=1\pmod p$.

This proof feels sloppy and even wrong, but it's the best way I can word out my intuition, may you please help me out?

$\endgroup$
  • $\begingroup$ Look at $a\cdot 1, a\cdot 2,...,a\cdot (p-1)$ modulo $p$. They are the same numbers as $1,2,...,p-1$ as a set (another ordering). Multiply them together and cancel what is cancel-able. $\endgroup$ – user530891 Feb 14 '18 at 22:58
  • $\begingroup$ It looks OK to me (though I am pretty tired right now). The way I learnt was to consider {1,2,3,…,p-1} and {a,2a,3a,…,(p-1)a} mod p. Prove that these sets are actually the same, by showing that no $na = ma$; then take the product of each set. $\endgroup$ – Patrick Stevens Feb 14 '18 at 22:58
  • $\begingroup$ thank you for your comments, but I am familiar with that proof already @PatrickStevens $\endgroup$ – Kam Feb 14 '18 at 23:03
  • $\begingroup$ @jfKeys thank you too! $\endgroup$ – Kam Feb 14 '18 at 23:03
  • 1
    $\begingroup$ I would abstract away the key part of the argument to prove: In any finite group $G$ of order $n$, for all $x \in G$, $x^n = e$. Then, applying that to the multiplicative group of units of $\mathbb{Z} / p \mathbb{Z}$ implies what you want to prove. $\endgroup$ – Daniel Schepler Feb 14 '18 at 23:31
4
$\begingroup$

This is basically correct, but some of your wording is confusing and can be cleaned up. Specifically, the following part:

we know that the order for all $a$ in the group $(Z_p,\times)$, is $x$ such that $a^x\equiv 1\pmod p$. We need to show that $x=p-1$.

Here you are being very ambiguous about what $x$ represents or what you want to be true of $x$. Is $x$ supposed to be the order of every element, or just of one particular element $a$? Also, if $x$ is the order of $a$, then $a^x\equiv 1\pmod p$, but the converse is not true. So the property that $a^x\equiv 1\pmod p$ does not uniquely define the order as you seem to be implying in the first sentence. On the other hand, if you are defining $x$ as the order, then the second sentence is just wrong: you don't want to prove that $x=p-1$. Instead, you want to show that $a^{p-1}\equiv 1\pmod p$, which does not necessarily mean that $x=p-1$.

I might rephrase this part as follows:

Let $a\in Z_p$ and let $x$ be the order of $a$. Then $a^x\equiv 1\pmod p$. We need to show that $a^{p-1}\equiv 1\pmod p$.

In particular, notice how my first sentence clearly and unambiguously introduces a specific element $a$ and defines $x$ as the order of $a$, rather than presenting a jumble of facts about $x$ indirectly. Only once the definition is made do I start discussing other facts.

$\endgroup$
  • $\begingroup$ Thank you so much for clearing this up! Might you have any advice for proper proof writing? Techniques, things to think about while writing them, how to read them etc? $\endgroup$ – Kam Feb 14 '18 at 23:10
  • 3
    $\begingroup$ Above all, be precise. Never say something unless you mean it literally. Define every new variable or concept you use clearly and precisely before you start using it. (Like all rules of writing, these rules can sometimes be bent some once you master them, but until then it's best to stick to them.) $\endgroup$ – Eric Wofsey Feb 14 '18 at 23:12
  • $\begingroup$ Thank you for your time and advice! $\endgroup$ – Kam Feb 14 '18 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.