The graph of the square mapping on the prime fields
type: Item
instance of: scholarly article
title: The graph of the square mapping on the prime fields
zbMATH Open document ID: 0843.05048
DOI: 10.1016/0012-365X(94)00250-M
author: Thomas D. Rogers
published in: Discrete Mathematics
publication date: 1996-03-24T00:00:00Z
review text: Let \(f: G\to G\) be a map of a finite set into itself. Then \(\text{graph}(G)\) is defined to be the directed graph whose vertices are the elements of \(G\) with a directed edge from \(x\) to \(f(x)\) for all \(x\in G\). In this paper, the action of the map \(f(x)= x^2\) on the multiplicative groups \(F^*_p\) of the prime fields is examined. Let \(C_m\) denote the cyclic group of order \(m\), and suppose that \(m\) is odd. Then \(\text{graph}(C_m)\) relative to \(f\) is the disjoint union \[ \text{graph}(C_m)= \bigcup_{d|m} \undersetbrace {\varphi(d)/\text{ord}_d 2}\to {(\sigma(\text{ord}_d 2)\cup\cdots\cup \sigma(\text{ord}_d 2))}, \] where \(\sigma(l)\) is the cycle of length \(l\), \(\varphi\) is Euler's function and \(\text{ord}_d2\) is the order of \(2\text{ mod } d\). Let \(n= 2^km\) where \(m\) is odd. Then \[ \text{graph}(C_m)= \bigcup_{d|m} \undersetbrace{\varphi(d)/\text{ord}_d 2}\to {(\sigma(\text{ord}_d 2, k)\cup\cdots \cup \sigma(\text{ord}_d 2, k))}, \] where \(\sigma(l, k)\) consists of a cycle of length \(l\) with a copy of the binary tree \(T_k\) of height \(k\) attached to each vertex.
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 858094
zbMATH Keywords: decomposition
zbMATH Keywords: cyclic group
zbMATH Keywords: cycle
zbMATH Keywords: tree
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: Groups, Graphs, and Fermat's Last Theorem
cites work: Q3222326
cites work: Q3689112
cites work: Q4039755
cites work: Q4039733
cites work: On ergodic one-dimensional cellular automata
cites work: Q4004187
cites work: Q3797922
description: scientific article; zbMATH DE number 858094