How many elements of the finite field $\mathbb{F}_{256}$ with 256 elements satisfy $x^{103}=x$?
How many elements in the finite field $F_{256}$ satisfy $x^{103}=x$?
4 Answers
Hint $\ $ The multiplicative group of $\rm\ \Bbb F_{256}\:$ is cyclic of order $255,$ so isomorphic to $\:\Bbb Z/255,\:$ where $\rm\:x^{102} = 1\:$ becomes $\rm\:102\, x\, \equiv\, 0\iff255\:|\:102\,x\iff 255\:|\:(255,102)\,x\, =\, 51\,x\iff 5\:|\:x,\: $ which has solutions $\rm\:x\, \equiv\, 5\,\{0,\ 1,\ 2,\ \ldots,\ 50\},\:$ for a total of $\,$ __ $\,$ solutions.
Remark $\ $ Note how the use $\:\Bbb Z/n\:$ as the canonical model of a cyclic group of order $\rm\:n\:$ serves to reduce group theory to number theory.
Well, $0$ is certainly a solution, and any nonzero solution would have to satisfy $x^{102} = 1$. So you can count the number of nonzero solutions using the fact that the multiplicative group $(\mathbb{F}_{256})^*$ is cyclic, and then add 1.
-
1+1 Nice hint to work on. – 2012-07-26
A finite multiplicative group contained in a field (in fact, in a domain) is always cyclic. In particular, the multiplicative subgroup of nonzero elements of $F_{256}$ is cyclic, of order $255 = 3\times 5\times 17$.
If $A$ is cyclic of order $k$, and $d|k$, then the set of elements whose order divides $d$ form a subgroup;they must form the unique cyclic subgroup of order $d$. If $\ell$ does not divide $k$, then the elements of order dividing $\ell$ are precisely the elements of order dividing $\gcd(\ell,k)$.
You are looking for the elements such that $x^{102}=1$ (well, and $0$...) Now, $\gcd(102,255) = 51$.
We will remember about the solution $x=0$ at the end. For the others, we want to solve $x^{102}=1$. The multiplicative group of non-zero elements of our field is cyclic. Let $g$ be a generator.
Note that $x^{102} =1$ iff $x^{\gcd(102,255)}=1$. This $\gcd$ is $51$.
Let $x=g^k$, where $0\le k \le 254$. Then $x^{51}=1$ iff $g^{51k}=1$. This is the case iff $255$ divides $51k$, that is, iff $5$ divides $k$.
So we need only count the multiples of $5$ between $0$ and $254$. Then add $1$.