The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$

Somer, Lawrence; Křížek, Michal

doi:10.1007/s10587-011-0079-x

Geodesic

Parcourir par

The structure of digraphs associated with the congruence

x^{k} \equiv y (\mod n)

Somer, Lawrence ; Křížek, Michal

Czechoslovak Mathematical Journal, Tome 61 (2011) no. 2, pp. 337-358.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

Résumé

We assign to each pair of positive integers

n

and

k \geq 2

a digraph

G (n, k)

whose set of vertices is

H = {0, 1, \dots, n - 1}

and for which there is a directed edge from

a \in H

b \in H

a^{k} \equiv b (\mod n)

. We investigate the structure of

G (n, k)

. In particular, upper bounds are given for the longest cycle in

G (n, k)

. We find subdigraphs of

G (n, k)

, called fundamental constituents of

G (n, k)

, for which all trees attached to cycle vertices are isomorphic.

MR Zbl

DOI : 10.1007/s10587-011-0079-x

Classification : 05C20, 11A07, 11A15, 20K01
Mots-clés : Sophie Germain primes; Fermat primes; primitive roots; Chinese Remainder Theorem; congruence; digraphs

@article{10_1007_s10587_011_0079_x,
     author = {Somer, Lawrence and K\v{r}{\'\i}\v{z}ek, Michal},
     title = {The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$},
     journal = {Czechoslovak Mathematical Journal},
     pages = {337--358},
     publisher = {mathdoc},
     volume = {61},
     number = {2},
     year = {2011},
     doi = {10.1007/s10587-011-0079-x},
     mrnumber = {2905408},
     zbl = {1249.11006},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1007/s10587-011-0079-x/}
}

TY  - JOUR
AU  - Somer, Lawrence
AU  - Křížek, Michal
TI  - The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$
JO  - Czechoslovak Mathematical Journal
PY  - 2011
SP  - 337
EP  - 358
VL  - 61
IS  - 2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/articles/10.1007/s10587-011-0079-x/
DO  - 10.1007/s10587-011-0079-x
LA  - en
ID  - 10_1007_s10587_011_0079_x
ER  -

%0 Journal Article
%A Somer, Lawrence
%A Křížek, Michal
%T The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$
%J Czechoslovak Mathematical Journal
%D 2011
%P 337-358
%V 61
%N 2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/articles/10.1007/s10587-011-0079-x/
%R 10.1007/s10587-011-0079-x
%G en
%F 10_1007_s10587_011_0079_x

Somer, Lawrence; Křížek, Michal. The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$. Czechoslovak Mathematical Journal, Tome 61 (2011) no. 2, pp. 337-358. doi : 10.1007/s10587-011-0079-x. https://geodesic-test.mathdoc.fr/articles/10.1007/s10587-011-0079-x/

Cité par Sources :