10.5.16

The rhythm of k mod n

The concept of the order of k mod n where k and n are integers such that k < n and GCD(k,n) = 1 relates to the smallest power of k for which k is 1 mod n. [page 242]

If GCD(k,n) > 1, or in other words, if k and n have common multiples then k is said to have an infinite order mod n.

The notion of infinite order suggests that if GCD(k,n)>1 then there is no predictable pattern in the kth row of the exponentiation table of Zn. However, empirical evidence suggests that this is not the case.



The need for the following definition arises.

Definition: The rhythm of k mod n is the smallest integer r > 1 such that kr = k mod n

Claim: The rhythm of k mod n is the number of unique integers that are powers of k mod n.

Proof. Given an integer k, then the next integer is k*k, and each subsequent integer is k*(k*k... mod n) until (k*k... mod n) = 1, therefore the rhythm of k mod n counts the number of unique integers that are powers of k mod n.

Also, clearly:

Claim: If GCD(k,n) = 1 and s is the order of k mod n then the rhythm r of k mod n is r = s+1

Proof: If s is the order of k mod n then ks = 1 mod n so ks+1 = k*(ks) = k*1= k mod n

Similarly, if r is the rhythm of k mod n and GCD(k,n) = 1 and then (r-1) is the order of k mod n

Claim: If r is the rhythm of k mod n and k divides n then kr-1 is a selfie square.

Proof: Coming soon

And now to the heartbreaking claim of the week. Heartbreaking because I found a counter example, which means that I'm wrong.

Claim: If n is the product of 2 distinct odd primes p and q then the rhythm of p is q and the rhythm of q is p
False n = 91 so p = 13 and q = 7

A small update to the algorithm for finding powers of k mod n now allows for k to be any integer smaller than n. Previously that algorithm only worked for GCD(k,n) = 1 but now I modified it to look for the rhythm of k mod n as opposed to the order, which only applies to k that has no common multiples with n.



/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate powers of k mod n, 
 generate the unique portion of row at k
 of the exponentiation table of Z sub n
 ---------------------------------------------------- */  

function powers_of_k_mod(n,k)
{
 var index = 0;
 var perm_slot = k;
 var count = 1;
 var perm = new Array(); var powers = new Array();
 perm = generate_permutation(n, k);
 powers.push(1);
 powers.push(perm_slot);
 //this ensures the initial k is counted
 //as well as k^r=k
 do
 {
    index = perm_slot;
    perm_slot = perm[index];
    powers.push(perm_slot); 
 }
 while(perm_slot != k && perm_slot != 0) 
 
 return powers;
}
 /* -----------------------------------------------
   generate kth row of the multiplication table 
   of Z sub n even if GCD(k,n)>1, which is shorter
-------------------------------------------------- */ 
function generate_permutation(n, k)
{
 var index = 0;
 var permutation = new Array();
 permutation.push(0);
 while(index!=(n-k))
 { 
   index = index + k;
   if (index > n) {
       index = index - n;       
   }
   permutation.push(index);
 }
 // this accounts for when n, k have common multiples
 if(n%k != 1)
 {
    for(i=0; i<(n-permutation.length); i++)
    { 
      permutation.push(permutation[i]);
    }    
 }  
  return permutation; 
}


UPDATE: This works for n that is either a product of distinct primes or a power of a prime because those two domains are of particular interest to me and this post in particular but I modified the algorithm above to also work for n that can be either a product of distinct primes or a power of a prime, or both so that now it can find the powers of any positive integer modulo any other positive integer.


/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate powers of k mod n, 
 generate the unique portion of row at k
 of the exponentiation table of Z sub n
 ---------------------------------------------------- */  

function powers_of_k_mod(n,k)
{
 var index = 0;
 var perm_slot = k;
 var count = 1;
 var perm = new Array(); var powers = new Array();
 perm = generate_permutation(n, k);
 powers.push(1);
 powers.push(perm_slot);
 do
 {
    index = perm_slot;
    perm_slot = perm[index];
    /* -------------------------------------------------
       this ensures that if there are any repetitions other than 1 and k
       within the powers array, then program terminates
    --------------------------------------------------- */
    if(powers.lastIndexOf(perm_slot) > 1)
    {return powers;}
    powers.push(perm_slot);      
 }
 while(perm_slot != k) 
 
 return powers;
}

 /* -----------------------------------------------
   generate kth row of the multiplication table 
   of Z sub n even if GCD(k,n)>1, which is shorter
-------------------------------------------------- */ 
function generate_permutation(n, k)
{
 var index = 0;
 var permutation = new Array();
 permutation.push(0);
 while(index!=(n-k))
 { 
   index = index + k;
   if (index > n) {
       index = index - n;       
   }
   permutation.push(index);
 }
 // this accounts for when n, k have common multiples
 if(n%k != 1)
 {
    for(i=0; i<(n-permutation.length); i++)
    { 
      permutation.push(permutation[i]);
    }    
 }  
  return permutation; 
}



ANOTHER UPDATE: Here's an algorithm for finding selfie squares using 3 calculations. Selfie squares have the shortest possible rhythm, and are either p or q or multiples of p or q.