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 k

^{th}row of the exponentiation table of Z

_{n}. 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 k

^{r}= 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 k

^{s}= 1 mod n so k

^{s+1}= k*(k

^{s}) = 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 k

^{r-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.