Idempotents and Congruence $$\boldsymbol{ax}\boldsymbol{ \equiv b\pmod n}$$

Štefan Porubský ()
Additional contact information
Štefan Porubský: Academy of Sciences of the Czech Republic, Institute of Computer Science

A chapter in From Arithmetic to Zeta-Functions, 2016, pp 385-403 from Springer

Abstract: Abstract Alomair et al. (J Math Cryptol 4(2):121–148, 2010, Lemma 3.1 ) noticed the following result which seems not to appear previously explicitly in the literature: Given a nonzero $$a \in \mathbb{Z}_{n}$$ , the ring of residues modulo n, such that gcd(a, n) = d | b, not only there exists an element $$x \in \mathbb{Z}_{n}$$ such that $$x \cdot a \equiv b\pmod n$$ , but that there even exists an invertible element $$x \in \mathbb{Z}_{n}^{{\ast}}$$ such that $$x \cdot a \equiv b\pmod n$$ . Their sufficient and necessary condition for this says that gcd(b∕d, n∕d) = 1 with d as above.A typical structure result on finite commutative semigroup says that the multiplicative semigroup of $$\mathbb{Z}_{n}$$ decomposes into the so-called maximal subsemigroups belonging to the idempotents of $$\mathbb{Z}_{n}$$ . Each such semigroup contains a maximal subgroup having for its identity the corresponding idempotent. In general this subgroup is a proper subset of the maximal subsemigroup containing it. However, the group of elements of $$\mathbb{Z}_{n}$$ coprime to n is an example of the case when this maximal subsemigroup and the maximal subgroup coincide (both evidently belonging to the idempotent 1).In what follows we prove that if a congruence $$x \cdot a \equiv b\pmod n$$ is solvable there always exists a solution in the maximal semigroup belonging to the idempotent given by the divisor δ = gcd(b∕d, n∕d) and if δ is a unitary divisor of n then there even exists a solution in the maximal subgroup belonging to the idempotent given by δ.

Keywords: Coprime; Idempotent; Maximal group; Maximal semigroup; Solution to a congruence; Primary 11A07; Secondary 11D04, 11A05, 20M14 (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-28203-9_23

Ordering information: This item can be ordered from
http://www.springer.com/9783319282039

DOI: 10.1007/978-3-319-28203-9_23

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().