2
$\begingroup$

For testing a particular algorithm I found mathematica is the best way as it has all the tools I need. I am stuck in a number theory part and since I am not an expert in mathematica I do not know how to write a code that seemingly involves loops. I want to pick random integers $a,b$ in interval $[T,2T]$ at $T>0$ and obtain $u,v\in\mathbb Z$ such that

  1. $au-bv=1$ (Euclidean algorithm)

  2. $au+bv$ is a prime

  3. $GCD(ab,uv)=1$

  4. $0<u,v<4T$

holds.

Is there simple enough code to do this?

It would help me to have 5. $a,b,u,v$ are all prime integers.

Improve this question
$\endgroup$
6
  • $\begingroup$ You realize there will very likely be an infinite number of such $u,v$ pairs? Or is just one instance enough? I suggest using the FindInstance[] function without any loops. $\endgroup$
    – Somos
    Commented Oct 11, 2020 at 18:30
  • 1
    $\begingroup$ There are so many conditions. If I know correct a and b find instance will work. Or else it is quadratic diophantine. $\endgroup$
    – Turbo
    Commented Oct 11, 2020 at 22:22
  • $\begingroup$ I think this is misworded. In general such u,v need not exist. Are you wanting code that will keep picking random a,b until you get a pair for which they do exist? $\endgroup$
    – Daniel Lichtblau
    Commented Oct 12, 2020 at 13:40
  • $\begingroup$ @DanielLichtblau Exactly. It appears mathematica is not very straightforward with procedural programming with loops. $\endgroup$
    – Turbo
    Commented Oct 12, 2020 at 14:17
  • $\begingroup$ (1) The coding is straightforward. One just needs to know the parameters of the problem. That is, are all of a,b,u,v sought or just, as it was worded, u and v? (2) Loops, should you wish to use them explicitly, can be accomplished with any of For, Do, and While. Same as in other languages. $\endgroup$
    – Daniel Lichtblau
    Commented Oct 12, 2020 at 14:44

1 Answer 1

Reset to default
3
$\begingroup$ 
primeVectors[max_, tries_] := Catch[Module[
   {a, b, done = False, tt = 0, u, v, egcd},
   While[! done && tt < tries,
    tt++;
    {a, b} = RandomInteger[{2, max}, 2];
    egcd = ExtendedGCD[a, b];
    If[egcd[[1]] =!= 1, Continue[]];
    {u, v} = {1, -1}*egcd[[2]];
    If[u < 0,
     {u, v} = {u, v} + {b, -a}; If[u < 0, Continue[]]];
    If[(! PrimeQ[a*u + b*v] || GCD[a*b, u*v] =!= 1), Continue[], 
     Throw[{{a, b}, {u, v}}]]
    ];
   $Failed
   ]]

examples:

SeedRandom[1234]
Table[primeVectors[1000, 15], 10]

(* Out[2247]= {{{899, 664}, {243, 329}}, $Failed, {{544, 
   695}, {359, -807}}, $Failed, $Failed, {{215, 
   571}, {409, -276}}, {{79, 347}, {123, 28}}, {{313, 555}, {172, 
   97}}, {{581, 155}, {151, -596}}, {{395, 313}, {42, 53}}} 7} *)
Improve this answer
$\endgroup$
5
  • $\begingroup$ This is a bit complicated as I am seeing for first time. So this address 1,2 and 4? $\endgroup$
    – Turbo
    Commented Oct 12, 2020 at 20:14
  • $\begingroup$ With "PrimeQ[au + bv] || GCD[ab, uv] =!= 1" seems address all of 1,2,3 and 4. Correct? $\endgroup$
    – Turbo
    Commented Oct 12, 2020 at 20:14
  • $\begingroup$ Yes, all four are addressed $\endgroup$
    – Daniel Lichtblau
    Commented Oct 12, 2020 at 20:31
  • $\begingroup$ May I ask how $a,b$ in $[T,2T]$ is guaranteed? I need a, b} = {a,b}=RandomInteger[{T,2T},2] correct? $\endgroup$
    – Turbo
    Commented Oct 13, 2020 at 20:22
  • $\begingroup$ I used max for your T. So they are selected to be less. If you want them in [T,2T] then that random generation needs to be modified slightly. $\endgroup$
    – Daniel Lichtblau
    Commented Oct 13, 2020 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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