Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FractionMod

Source Notebook

Get a congruent integer for a given fraction and modulus

Contributed by: Ed Pegg Jr

ResourceFunction["FractionMod"][a/b,n]

returns such that .

Details

If and GCD[b,n]=1 (i.e. b and n are coprime), then .
ResourceFunction["FractionMod"] is frequently used in cryptography.

Examples

Basic Examples (2) 

7×3 (mod 16) equals 5:

In[1]:=
Mod[7 3, 16]
Out[1]=

Similarly, the fractional modulus of 3/5 (mod 16) equals 7:

In[2]:=
ResourceFunction["FractionMod"][3/5, 16]
Out[2]=

As expected, adding 16 gives the same result (mod 16):

In[3]:=
ResourceFunction["FractionMod"][16 + 3/5, 16]
Out[3]=

A grid of fractions, moduli and fractional moduli:

In[4]:=
Grid[Transpose[{#[[1]]/#[[2]], #[[3]], ResourceFunction["FractionMod"][#[[1]]/#[[2]], #[[3]]]} & /@ Partition[Prime[Range[25]], 3, 1]], Frame -> All]
Out[4]=

Scope (2) 

A range of fractional moduli (mod 8) with tooltips:

In[5]:=
farey = Select[Drop[FareySequence[19], 1], GCD[Denominator[#], 8] == 1 &]; mods = {#, ResourceFunction["FractionMod"][#, 8]} & /@ farey; Graphics[Tooltip[Disk[#/{1, 16}, .02], #] & /@ mods]
Out[5]=

A few of the fractions and their fractional moduli (mod 8):

In[6]:=
RandomSample[mods, 7]
Out[6]=

Neat Examples (1) 

The fractional moduli of a series of prime denominator fractions gives a shuffling of the integer range:

In[7]:=
Column[Table[ ResourceFunction["FractionMod"][1/#, Prime[k]] & /@ Range[Prime[k] - 1], {k, 3, 10}]]
Out[7]=

Version History

  • 1.0.0 – 11 October 2021

Related Resources

License Information