A generalization of Euler’s Criterion to composite moduli

József Vass
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 22, 2016, Number 3, Pages 9–19
Full paper (PDF, 150 Kb)

Details

Authors and affiliations

József Vass
Department of Algebra and Number Theory, Eötvös Loránd University
Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary

Abstract

A necessary and sufficient condition is provided for the solvability of a binomial congruence with a composite modulus, circumventing its prime factorization. This is a generalization of Euler’s Criterion through that of Euler’s Theorem, and the concepts of order and primitive roots. Idempotent numbers play a central role in this effort.

Keywords

• Binomial congruences
• Power residues
• Generalized primitive roots

AMS Classification

• 11A15
• 11A07
• 11C08

References

1. Alkam, O. and Osba, E. A. (2008) On the regular elements in ℤ_n. Turkish Journal of Mathematics, 32(1):31–39.
2. Andrews, G. E. (1971) Number Theory. W.B. Saunders Company.
3. Euler, L. (1750) Theoremata circa divisores numerorum. Novi Commentarii academiae scientiarum Petropolitanae, 1:20–48.
4. Euler, L. (1761) Theoremata circa residua ex divisione potestatum relicta. Novi Commentarii academiae scientiarum Petropolitanae, 7:49–82.
5. Euler, L. (1763) Theoremata arithmetica nova methodo demonstrata. Novi Commentarii academiae scientiarum Petropolitanae, 8:74–104.
6. Gauss, C. F. (1801) Disquisitiones Arithmeticae.1986, Springer-Verlag, New York.
7. Harger, R. T. and Harvey, M. E. (2003) A generalization of the Euler–Fermat theorem. International Journal of Mathematical Education in Science and Technology, 34(6):949– 951.
8. Kalmár, L. (1936) A számelmélet alaptételéről. Matematikai és Fizikai Lapok, 43:27–45.
9. Kløve, T. (1976) A generalization of Euler’s theorem. Portugaliae Mathematica, 35(2):111– 112.
10. Lemmermeyer, F. (2000) Reciprocity laws: from Euler to Eisenstein. Springer Science & Business Media.
11. Livingston, A. and Livingston, M. (1978) The congruence ar+s  ar (mod m). The American Mathematical Monthly, 85(2):97–100.
12. Morgado, J. (1972) Inteiros regulares módulo n. Gazeta de Matematica (Lisboa), 33(125- 128):1–5.
13. Morgado, J. (1974) A property of the Euler ‘-function concerning the integers which are regular modulo n. Portugaliae Mathematica, 33(4):185–191.
14. Morgado, J. (1976) Another generalization of Euler’s theorem. Portugaliae Mathematica, 35(4):241–243.
15. Morgado, J. (1977) Some remarks on two generalizations of Euler’s theorem. Portugaliae Mathematica, 36(2):153–158.
16. Osborn, R. (1974) A “good” generalization of the Euler-Fermat theorem. Mathematics Magazine, 47(1):28–31.
17. Sándor, J. and Crstici, B. (2004) Handbook of Number Theory II, volume 2. Springer Science & Business Media.
18. Szele, T. (1948) Une généralisation de la congruence de Fermat. Matematisk tidsskrift. B, pages 57–59.
19. Tóth, L. (2008) Regular integers (mod n). Annales Univ. Sci. Budapest., Sect. Comp., 29:263–275.
20. Tóth, L. (2013) A bibliography of papers and other sources on regular integers modulo n. ResearchGate.
21. Vass, J. (2004) On composite moduli from the viewpoint of idempotent numbers. Master’s thesis, Eötvös Loránd University.
22. von Neumann, J. (1936) On regular rings. Proceedings of the National Academy of Sciences, 22(12):707–713.
23. Weaver, M. W. (1952) Cosets in a semi-group. Mathematics Magazine, 25(3):125–136.
24. Weisstein, E. W. Discrete logarithm. MathWorld – A Wolfram Web Resource.