9.6.16

Finding An Integer With The Shortest Rhythm

In my previous post I talked about the rhythm of an element k mod n, which I defined as the smallest integer r greater than 1 for which k^r = k mod n.

If n is the product of 2 distinct primes then every integer k smaller than n has a rhythm. If n is any other integer, then all k < n such that GCD(k,n) = 1 have a rhythm. Of particular interest are the integers with the shortest or the smallest possible rhythm.

Since r must be greater than 1 by definition then the smallest possible rhythm r is 2, and therefore the integers with the smallest rhythm are the integers, for which k^2 = k mod n

Claim: If n is the product of two distinct primes p < q then (((n-1)/2)+1)2 has exactly 4 square roots.

Claim: If n is the product of two distinct primes p < q and m=(((n-1)/2)+1) + TheSmallestSquareRootOf((((n-1)/2)+1)2 mod n) mod n then m is either equal to q or m is a small multiple of q such that m2 = m mod n

Furthermore, if w = (((n-1)/2)+1) - TheSmallestSquareRootOf((((n-1)/2)+1)2 mod n) mod n then w is either equal to p or w is a small multiple of p such that w2 = w mod n

Example:
i) Let n = 35 so p = 5, q = 7
then m = (((35-1)/2)+1) + TheSmallestSquareRootOf((((35-1)/2)+1)2 mod 35) mod 35
            = (18 + TheSmallestSquareRootOf((18)2 mod 35) mod 35
            = (18 + TheSmallestSquareRootOf(9) mod 35) mod 35
            = (18 + 3) mod 35
            = 21 mod 35

and 212 = 21 mod 35, also 21 = 7*3

ii) Let n = 77, so p = 7, q = 11
then m = (((77-1)/2)+1) + TheSmallestSquareRootOf((((77-1)/2)+1)2 mod 77) mod 77  =
            = (39 + TheSmallestSquareRootOf((39)2 mod 77) mod 77
            = (39 + TheSmallestSquareRootOf(58) mod 77) mod 77
            = (39 + 17) mod 35   [since 172 = 58 mod 77]
            = 56 mod 35

and 562 = 56 mod 77, also 56 = 7*8



So an algorithm for finding an integer m with the smallest rhythm would involve the following steps:

  1.  Calculate k=(((n-1)/2)+1) 
  2.  Calculate b = the smallest square root of((((n-1)/2)+1)2 mod n)
  3.  Return m = k + b mod n