1
$\begingroup$

Suppose $x_1 , x_2 \in \Bbb{F}_{p^n}^*$. Let $f_i$ be the order of $x_i$ in the cyclic group $\Bbb{F}_{p^n}^*$. Using Bezout's identity we find an $\alpha$ and a $\beta$ such that $\alpha f_1 + \beta f_2=gcd(f_1,f_2)$. Suppose $x=x_1^\beta x_2^\alpha$. How do we prove that $x^{\frac{lcm(f_1,f_2)}{f_i}} = x_i$ for $1\leq i \leq 2$?

I tried by finding a generator $\omega$ of the cyclic group. Then $x_1=\omega^{k_1}$ for a certain $k_1$ and $x_2=\omega^{k_2}$ for a certain $k_2$. Thus we have $x=\omega^{(\alpha k_1 + \beta k_2)}$. We also have that $lcm(f_1,f_2)=\frac{f_1*f_2}{gcd(f1,f2)} = \frac{f_1*f_2}{\alpha f_1 + \beta f_2}$. So $x^{\frac{lcm(f_1,f_2)}{f_1}}= x^{\frac{f_2}{\alpha f_1 + \beta f_2}} = \omega^{\left(\frac{f_2(\alpha k_1+\beta k_2)}{\alpha f_1 + \beta f_2}\right)}$. How do I continue ? or is this the wrong direction ?

$\endgroup$
  • 1
    $\begingroup$ As stated, the claim is false I think? If $x_1, x_2$ have equal order but different values, then the exponent is the same for both. Consider the theorem with $x_1= a, x_2=a+1$ with $p=2, n=2$. Both have order 3, so the LCM is 3, and the exponent is the same for all i, so we get $a=a+1$, which is a contradiction. $\endgroup$ – Artimis Fowl May 7 '17 at 18:48
0
$\begingroup$

The following is a partial solution - I believe the claim is missing some constraint on $f_i$ or possibly $i$.

One can get close with just the given $x = x_1^\alpha x_2^\beta$. Note that $d = gcd(f_1, f_2)$ divides $lcm(f_1, f_2), f_1, f_2$. Let's assume WLOG $i=1$. Note:

$$\frac{lcm(f_1,f_2)}{f_1} = \frac{f_2}{d}$$

So we can simplify the exponent, and use our defined value of $x$:

$$x_1^{\beta f_2 / d} x_2^{\alpha f_2 / d} = x_1^{1 - \alpha f_1 / d} x_2^{\alpha f_2/d} = x_1 \frac{x_2^{\alpha f_2 / d}}{x_1^{\alpha f_1 / d}}$$

The second step there used $d = \alpha f_1 + \beta f_2 \implies d - \alpha f_1 = \beta f_2 $, and distributed the $/d$. The last equality is just rearranging.

Now, we're finished if we can show $\frac{x_1^{\alpha f_1 / d}}{x_2^{\alpha f_2 / d}} = \sqrt[d]{1} = 1$. Ie, that $y^d = 1$ has only one solution in $\mathbb{F}_{p^i}$. Unfortunately this needn't be the case, take for example $\alpha, 1+ \alpha$ in $\mathbb{F}_4$. $d=3$, and cube roots are not unique. In fact the ending equation need not satisfy...

$\endgroup$

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.