-1

How can I approach a question of the form
Can there exist an element β in Zx satisfying $$ β^a= b $$

and $$ β^c= d $$?
I understand how to find primitive elements of Zx and could use it to find β if I was given just 1 of these equations that have to be satisfied, but don't see how that helps me as β doesn't necessarily have to be primitive to satisfy them.

Is there any way I can approach this without brute forcing this?
Thanks

Note: I know everything except β not looking for an answer just the approach

Seán Ward
  • 3

1 Answers1

-1

A general approach that is quite powerful here is to consider the gcd of $a$,$c$ — or more generally, that of $a$,$c$,$\phi(x)$ (assuming that $a$,$c$ don’t already divide $\phi(x)$, which is hard to tell from the information you’ve suppressed).

Suppose $g$ is this gcd. Then there exists integers $r,s$ such that

$$ra + sc = g.$$

This allows you to combine the two equations into their lowest-degree form:

$$\beta^g = b^r d^s.$$

First, you can do a consistency check: if the RHS evaluates to $m$, does $m^{a/g} = b$ and $m^{c/g} = d$? If not, then the equations are clearly inconsistent.

If it does pass these tests then you have reduced the two equations down to one that is easier to check for (it has lower degree).

Assuming that $b,d$ are relatively prime to $x$ (again hard to say due to the suppression of details), then you can also combine this with the third equation $\beta^{\phi(x)} = 1$.

Erick Wong
  • 25,198
  • 3
  • 37
  • 91
  • Hi thanks for your answer, All of a,c,x are prime so the gcd is 1. What is m in your answer? (If it helps you to explain anything the values are β^13 = 2, β^11 = 7 all in Z_47) – Seán Ward Aug 07 '19 at 20:34
  • $m$ is the RHS of the previous equation, $b^r d^s$. – Erick Wong Aug 07 '19 at 20:54
  • Why would someone downvote this answer? How weird. – Erick Wong Aug 07 '19 at 20:55
  • If $a,c$ are relatively prime as in your case, then this completely determines the value of $\beta$ (which may or may not actually work, but that is trivial to check). – Erick Wong Aug 07 '19 at 20:57
  • Thanks again for your reply, not sure why someone would downvote you trying to help...However I am still confused. How do I find what r and s are without just brute forcing it? – Seán Ward Aug 07 '19 at 21:53
  • @SeánWard Read up about Extended Euclidean Algorithm. $r$ and $s$ can be found in just $O(\text{num of digits of } a)$ steps. – Erick Wong Aug 07 '19 at 21:56
  • Oh right I should have copped that...I understand now. Thank you so much for all your help – Seán Ward Aug 07 '19 at 22:23