Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many elements of the finite field $\mathbb{F}_{256}$ with 256 elements satisfy $x^{103}=x$?

share|improve this question

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
+1 Nice hint to work on. –  DonAntonio Jul 26 '12 at 2:33

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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