2.5.16

Lonely powers, selfie squares

Definition: Given n, k such that n < k, then k is a lonely power mod n if k to the power of k is congruent to 1 mod n. In other words, if kk = 1 mod n then k is a lonely power mod n

Example:
i) In Z35 there are 5 non-trivial lonely powers mod n, namely 6, 8, 12, 24, 34 since 66 = 1 mod 35, 88 = 1 mod 35, 1212 = 1 mod 35, 2424 = 1 mod 35, 3434 = 1 mod 35
ii) In Z15 there are 3 non-trivial lonely powers mod n, namely 4, 8, and 14
iii) In Z11 there are 2 non-trivial lonely powers mod n, namely 5 and 10
iv) In Z25 there is only 1 non-trivial lonely power mod , namely 24


Note: Not all lonely squares are lonely powers (for example: 432 = 1 mod 77 but 4343 = 43 mod 77)
Similarly, not all lonely powers are lonely squares (for example: 88 = 1 mod 35 but 82 = 29 mod 35)

Claim: If r is the smallest integer such that kr = 1 mod n and r divides k then k is a lonely power.

Proof: Since r divides k then k = r*b for some integer b < k and kr = 1 mod n so therefore:

kk = kr*b = (kr)b = 1b = 1 mod n ,',



Definition: Given k < n, then k is a selfie square mod n if k2 = k mod n

Example:
i) In Z35 there are 2 non-trivial selfie squares mod n, namely 15 and 21 since 152 = 15 mod 35, 212 = 21 mod 35
ii) In Z15 there are 2 non-trivial selfie squares mod n, namely 6 and 10 since 62 = 6 mod 15, 102 = 10 mod 15
iii) In Z11 there are no non-trivial selfies square mod n
iv) In Z25 there are no non-trivial selfies square mod n

I previously discussed selfie squares here but I made a few new observations recently.

Claim: If n is the product of two distinct odd primes p and q then there are (at least) 2 non-trivial selfie squares mod n such that if the first non-trivial selfie square k1 is at a distance d from the (((n-1)/2)+1)th element then there exists another selfie square k2 = (((n-1)/2)+1) + d

edited the algorithm presented in this post to find the second selfie square mod n.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find selfie squares in Zn
 ---------------------------------------------------- */  
 
function a_equal_to_a_squared_mod(n)
{
   var index = 0;
   var cur = (n-1)/2;
   var squares = new Array();
   var squared =(((n-1)/2)*((n-1)/2))%n;
   while( squared != cur && squared != 0)
    {
     index = index + 1;
     squared = (squared + 2*index)%n;
     cur = cur - 1;
    }
   //if there exists one selfie square at
   //distance d from (((n-1)/2)+1)th element
   cur = ((((n-1)/2)+1) - squared);
   //then there exist another one
   //at (((n-1)/2)+1) + distance d 
   cur = (((n-1)/2)+1) + cur;
   squares.push(squared);
   squares.push(cur);
   return squares;
}