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.

$\endgroup$
  • $\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 Oct 11 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$ – a.. Oct 11 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 Oct 12 at 13:40
  • $\begingroup$ @DanielLichtblau Exactly. It appears mathematica is not very straightforward with procedural programming with loops. $\endgroup$ – a.. Oct 12 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 Oct 12 at 14:44
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$
  • $\begingroup$ This is a bit complicated as I am seeing for first time. So this address 1,2 and 4? $\endgroup$ – a.. Oct 12 at 20:14
  • $\begingroup$ With "PrimeQ[au + bv] || GCD[ab, uv] =!= 1" seems address all of 1,2,3 and 4. Correct? $\endgroup$ – a.. Oct 12 at 20:14
  • $\begingroup$ Yes, all four are addressed $\endgroup$ – Daniel Lichtblau Oct 12 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$ – a.. Oct 13 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 Oct 13 at 21:35

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.