text:
Hegemony

Hegemony is the political, economic, and military predominance of one state over other states, either regional or global.

In Ancient Greece (ca. 8th BC – AD 6th c.), hegemony denoted the politico-military dominance of the hegemon city-state over other city-states. In the 19th century, hegemony denoted the "social or cultural predominance or ascendancy; predominance by one group within a society or milieu" and "a group or regime which exerts undue influence within a society".

In theories of imperialism, the hegemonic order dictates the internal politics and the societal character of the subordinate states that constitute the hegemonic sphere of influence, either by an internal, sponsored government or by an external, installed government. The term hegemonism denoted the geopolitical and the cultural predominance of one country over other countries, e.g. the hegemony of the Great Powers established with European colonialism in Africa, Asia, and Latin America. In International Relations theories, hegemony is distinguished from empire as ruling only external but not internal affairs of other states.

Etymology
From the post-classical Latin word (1513 or earlier) from the Greek word hēgemonía, related to the word ἡγεμών, hēgemṓn, leader.

30th–27th centuries BC
The political pattern of Sumer was hegemony shifting from city to city and called King of Kish. According to the Sumerian King List, Kish established the hegemony yet before the Flood. One of the earliest literary legacies of humankind, the Epic of Gilgamesh, is a case of anti-hegemonic resistance. Gilgamesh fights and overthrows the hegemon of his world.

8th–3rd centuries BC
In the Greek world of 5th century BC, the city-state of Sparta was the hegemon of the Peloponnesian League (6th to 4th centuries BC) and King Philip II of Macedon was the hegemon of the League of Corinth in 337 BC (a kingship he willed to his son, Alexander the Great). Likewise, the role of Athens within the short-lived Delian League (478–404 BC) was that of a "hegemon". The super-regional Persian Achaemenid Empire of 550 BC–330 BC dominated these sub-regional hegemonies prior to its collapse. Ancient historians such as Herodotus (c. 484 BC – c. 425 BC). Xenophon (c. 431 BC – 354 BC) and Ephorus (c. 400 BC – 330 BC) pioneered the use of the term hēgemonía in the modern sense of hegemony.

In Ancient East Asia, Chinese hegemony existed during the Spring and Autumn period (c. 770–480 BC), when the weakened rule of the Eastern Zhou Dynasty led to the relative autonomy of the Five Hegemons (Ba in Chinese [霸]). The term is translated as lord protector, or lord of the covenants, or chief of the feudal lords and is described as intermediate between king of independent state and Emperor of All under Heaven. The hegemons were appointed by feudal lord conferences and were nominally obliged to support the King of Zhou, whose status parallel to that of the Roman Pope in the medieval Europe.

In 364 BC, Qin emerged victorious from war and its Duke Xian (424–362 BC) was named hegemon by the King of Zhou. Qin rulers did not preserve the official title of hegemon but in fact kept the hegemony over their world: "For more than one hundred years [before 221 BC] Qin commanded eight lands and brought the lord of equal rank to its court." One of the six other great powers, Wei, was annexed as early as 324 BC. From the reign of Duke Xian on, "Qin gradually swallowed up the six [other] states until, after hundred years or so, the First Emperor was able to bring all kings under his power."

The century preceding the Qin's wars of unification in 221 BC was dominated by confrontation between the hegemonic horizontal alliance led by Qin and the anti-hegemonic alliance called perpendicular or vertical. "The political world appears as a chaos of ever-changing coalitions, but in which each new combination could ultimately be defined by its relation to Qin."

The first anti-hegemonic or perpendicular alliance was formed in 322 BC. Qin was supported by one state, Wei, which it had annexed two years previously. The remaining five great warring states of China joined in the anti-hegemonic coalition and attacked Qin in 318 BC. "Qin, supported by one annexed state, overwhelmed the world coalition." The same scenario repeated itself several times. ) until Qin decisively moved from hegemony to conquests and annexations in 221 BC.

2nd century BC – 15th century AD
Rome established its hegemony over the entire Mediterranean after its victory over the Seleucid Empire in 189 BC. Officially, Rome's client states were outside the whole Roman imperium, and preserved their entire sovereignty and international rights and privileges.

With few exceptions, the Roman treaties with client states (foedera) were formulized on equal terms without any expression of clientship and the Romans almost never used the word "client." The term "client king" is an invention of the post-Renaissance scholarship. Those who are conventionally called by modern historians of Rome "client kings" were referred to as "allies and friends" of the Roman people. "Alliance" and "friendship," not any kind of subordination, bound them to Rome.

No regular or formal tribute was extracted from client states. The land of a client state could not officially be a basis for taxation. The overall fact is that, despite extensive conquests, the Romans did not settle down nor extracted revenues in any subdued territories between 200 and 148 BC. The first good evidence for regular taxation of another kingdom comes from Judea as late as 64 BC.

The Roman hegemony of the late Republic left to the Mediterranean kings internal autonomy and obliged not to enter hostile to Rome alliances and not to wage offensive wars without consent of the Senate. Annexations usually followed when client kings broke this order (Macedonia in 148 BC and Pontus in 64 BC). In the course of these and other annexations, Rome gradually evolved from hegemony into empire. The last major client state of the Mediterranean – the Ptolemaic Kingdom – was annexed by Augustus in the very beginning of his reign in 30 BC.

Augustus initiated an unprecedented era of peace, shortly after his reign called Pax Romana. This peace however was imperial rather than hegemonic. Classic and modern scholars who call Pax Romana "hegemonic peace," use the term "hegemony" in its broader sense which includes both hegemony and empire.

From the 7th century to the 12th century, the Umayyad Caliphate and later Abbasid Caliphate dominated the vast territories they governed, with other states like the Byzantine Empire paying tribute.

In 7th century India, Harsha, ruler of a large empire in northern India from AD 606 to 647, brought most of the north under his hegemony. He preferred not to rule as a central government, but left "conquered kings on their thrones and contenting himself with tribute and homage."

From the late 9th to the early 11th century, the empire developed by Charlemagne achieved hegemony in Europe, with dominance over France, most of Northern and Central Italy, Burgundy and Germany.

From the 11th to the late 15th centuries the Italian maritime republics, in particular Venice and Genoa held hegemony in the Mediterranean, dominating trade between Europe and the Orient for centuries, and having naval supremacy. However, with the arrival of the Age of Discovery and the Early modern period, they began to gradually lose their hegemony to other European powers.

16th–19th centuries
In The Rise of the Qi Ye Ji Tuan and the Emergence of Chinese Hegemony Jayantha Jayman writes, "If we consider the Western dominated global system from as early as the 15th century, there have been several hegemonic powers and contenders that have attempted to create the world order in their own images." He lists several contenders for historical hegemony:
 * Portugal 1494 to 1580 (From the end of the Italian Wars to Spanish-Portuguese Union). Based on Portugal's dominance in navigation.
 * Spain 1516 to 1659 (From the accession of Charles I of Spain to the Treaty of the Pyrenees). Based on the Spanish dominance of the European battlefields and the global exploration and colonization of the New World.
 * The Netherlands 1580 to 1688 (From the 1579 Treaty of Utrecht, which marks the foundation of the Dutch Republic, to the Glorious Revolution, William of Orange's arrival in England). Based on Dutch control of credit and money.
 * France 1643 to 1763 (From the accession of Louis XIV to the end of the Seven Years' War).
 * Britain 1688 to 1792 (From the Glorious Revolution to the start of the French Revolutionary Wars). Based on British textiles and command of the high seas.
 * French Revolution and Napoleonic France (1789 to 1815).
 * Britain 1815 to 1914 (From the Congress of Vienna to the start of the Great War). Based on British industrial supremacy and railroads.

Phillip IV tried to restore the Habsburg dominance but, by the middle of the 17th century "Spain's pretensions to hegemony (in Europe) had definitely and irremediably failed." In late 16th- and 17th-century Holland, the Dutch Republic's mercantilist dominion was an early instance of commercial hegemony, made feasible by the development of wind power for the efficient production and delivery of goods and services. This, in turn, made possible the Amsterdam stock market and concomitant dominance of world trade.

In France, King Louis XIV (1638–1715) and (Emperor) Napoleon I (1799–1815) attempted true French hegemony via economic, cultural and military domination of most of Continental Europe. However, Jeremy Black writes that, because of Britain, France "was unable to enjoy the benefits" of this hegemony. After the defeat and exile of Napoleon, hegemony largely passed to the British Empire, which became the largest empire in history, with Queen Victoria (1837–1901) ruling over one-quarter of the world's land and population at its zenith. Like the Dutch, the British Empire was primarily seaborne; many British possessions were located around the rim of the Indian Ocean, as well as numerous islands in the Pacific Ocean and the Caribbean Sea. Britain also controlled the Indian subcontinent and large portions of Africa.

In Europe, Germany, rather than Britain, may have been the strongest power after 1871, but Samuel Newland writes:"Bismarck defined the road ahead as … no expansion, no push for hegemony in Europe. Germany was to be the strongest power in Europe but without being a hegemon. … His basic axioms were first, no conflict among major powers in Central Europe; and second, German security without German hegemony.'"

These fluctuations form the basis for cyclical theories by George Modelski and Joshua S. Goldstein, both of whom allege that naval power is vital for hegemony.

20th century
The early 20th century, like the late 19th century, was characterized by multiple Great Powers but no global hegemon. World War I strengthened the United States and, to a lesser extent, Japan. Both of these states' governments pursued policies to expand their regional spheres of influence, the US in Latin America and Japan in East Asia. France, the UK, Italy, the Soviet Union and later Nazi Germany (1933–1945) all either maintained imperialist policies based on spheres of influence or attempted to conquer territory but none achieved the status of a global hegemonic power.

After the Second World War, the United Nations was established and the five strongest global powers (China, France, the UK, the US, and the USSR) were given permanent seats on the U.N. Security Council, the organization's most powerful decision-making body.

Following the war, the US and the USSR were the two strongest global powers and this created a bi-polar power dynamic in international affairs, commonly referred to as the Cold War. American hegemony during this time has been described as "Empire by invitation". The hegemonic conflict was ideological, between communism and capitalism, as well as geopolitical, between the Warsaw Pact countries (1955–1991) and NATO/SEATO/CENTO countries (1949–present/1954–1977/1955–1979). During the Cold War both hegemons competed against each other directly (during the arms race) and indirectly (via proxy wars). The result was that many countries, no matter how remote, were drawn into the conflict when it was suspected that their government's policies might destabilize the balance of power. Reinhard Hildebrandt calls this a period of "dual-hegemony", where "two dominant states have been stabilizing their European spheres of influence against and alongside each other." Proxy wars became battle grounds between forces supported either directly or indirectly by the hegemonic powers and included the Korean War, the Laotian Civil War, the Arab–Israeli conflict, the Vietnam War, the Afghan War, the Angolan Civil War, and the Central American Civil Wars.

Following the dissolution of the Soviet Union in 1991, the United States was the world's sole hegemonic power.

21st century
Various perspectives on whether the US was or continues to be a hegemon have been presented since the end of the Cold War. Most notably, American political scientists John Mearsheimer and Joseph Nye have argued that the US is not a genuine global hegemon because it has neither the financial nor the military resources to impose a proper, formal, global hegemony. This theory is heavily contested in academic discussions of international relations, with Anna Beyer being a notable critic of Nye and Mearsheimer.

The French Socialist politician Hubert Védrine in 1999 described the US as a hegemonic hyperpower, because of its unilateral military actions worldwide.

Pentagon strategist Edward Luttwak, in The Grand Strategy of the Roman Empire, outlined three stages, with hegemonic being the first, followed by imperial. In his view the transformation proved to be fatal and eventually led to the fall of the Roman Empire. His book gives implicit advice to Washington to continue the present hegemonic strategy and refrain from establishing an empire.

In 2006, author Zhu Zhiqun claimed that China is already on the way to becoming the world hegemon and that the focus should be on how a peaceful transfer of power can be achieved between the US and China, but has faced opposition to this claim. According to the recent study published in 2019, the authors argued that a "third‐way hegemony" or Dutch‐style hegemony apart from a peaceful or violent hegemonic rise may be the most feasible option to describe China in its global hegemony in the future.

Political science

In the historical writing of the 19th century, the denotation of hegemony extended to describe the predominance of one country upon other countries; and, by extension, hegemonism denoted the Great Power politics (c. 1880s – 1914) for establishing hegemony (indirect imperial rule), that then leads to a definition of imperialism (direct foreign rule).

In the early 20th century, the Italian Marxist philosopher Antonio Gramsci used the idea of hegemony to talk about politics within a given society. He developed the theory of cultural hegemony, an analysis of economic class (including social class) and how the ruling class uses consent as well as force to maintain its power. Hence, the philosophic and sociologic theory of cultural hegemony analysed the social norms that established the social structures to impose their Weltanschauung (world view)—justifying the social, political, and economic status quo—as natural, inevitable, and beneficial to every social class, rather than as artificial social constructs beneficial solely to the ruling class.

From the Gramsci analysis derived the political science denotation of hegemony as leadership; thus, the historical example of Prussia as the militarily and culturally predominant province of the German Empire (1871–1918); and the personal and intellectual predominance of Napoleon Bonaparte upon the French Consulate (1799–1804). Contemporarily, in Hegemony and Socialist Strategy (1985), Ernesto Laclau and Chantal Mouffe defined hegemony as a political relationship of power wherein a sub-ordinate society (collectivity) perform social tasks that are culturally unnatural and not beneficial to them, but that are in exclusive benefit to the imperial interests of the hegemon, the superior, ordinate power; hegemony is a military, political, and economic relationship that occurs as an articulation within political discourse. Beyer analysed the contemporary hegemony of the United States at the example of the Global War on Terrorism and presented the mechanisms and processes of American exercise of power in 'hegemonic governance'.

According to John Mearsheimer, global hegemony is unlikely due to the difficulties in projecting power over large bodies of water.

International relations
In the field of International Relations, hegemony generally refers to the ability of an actor to shape the international system. Usually this actor is a state, such as Britain in the 19th century or the United States in the 20th century. A hegemon may shape the international system through coercive and non-coercive means. According to Nuno Monteiro, hegemony is distinct from unipolarity. The latter refers to a preponderance of power within an anarchic system, whereas the former refers to a hierarchical system where the most powerful state has the ability to "control the external behavior of all other states."

The English school of international relations takes a broader view of history. The research of Adam Watson was world-historical in scope. For him, hegemony was the most common order in history (historical "optimum") because many provinces of "frank" empires were under hegemonic rather than imperial rule. Watson summarized his life-long research: There was a spectrum of political systems ranging between multiple independent states and universal empire. The further a political system evolved towards one of the extremes, the greater was the gravitational pull towards the hegemonic center of the spectrum.

Hegemony may take different forms. Benevolent hegemons provide public goods to the countries within their sphere of influence. Coercive hegemons exert their economic or military power to discipline unruly or free-riding countries in their sphere of influence. Exploitative hegemonies extract resources from other countries. A prominent theory in International Relations focusing on the role of hegemonies is hegemonic stability theory. Its premise is that a hegemonic power is necessary to develop and uphold a stable international political and economic order. The theory was developed in the 1970s by Robert Gilpin and Stephen D. Krasner, among others. It has been criticized on both conceptual and empirical grounds. For example, Robert Keohane has argued that the theory is not a proper theory because it amounts to a series of allegedly redundant claims that apparently could not be used predictively.

A number of International Relations scholars have examined the decline of hegemons and their orders. For some, such decline tends to be disruptive because the stability that the hegemon provided gives way to a power vacuum. Others have maintained that cooperation may persist in the face of hegemonic decline because of institutions or enhanced contributions from non-hegemonic powers.

There has been a long debate in the field about whether American hegemony is in decline. As early as in the 1970s, Robert Gilpin suggested that the global order maintained by the United States would eventually decline as benefits from the public goods provided by Washington would diffuse to other states. In the 1980s, some scholars singled out Japan's economic growth and technological sophistication as a threat to U.S. primacy. More recently, analysts have focused on the economic and military rise of China and its challenge to U.S. hegemony.

Scholars differ as to whether bipolarity or unipolarity is likely to produce the most stable and peaceful outcomes. Kenneth Waltz and John Mearsheimer are among those who argue that bipolarity tends to generate relatively more stability, whereas John Ikenberry and William Wohlforth are among those arguing for the stabilizing impact of unipolarity. Some scholars, such as Karl Deutsch and J. David Singer argued that multipolarity was the most stable structure.

Scholars disagree about the sources and stability of U.S. unipolarity. Realist international relations scholars argue that unipolarity is rooted in the superiority of U.S. material power since the end of the Cold War. Liberal international relations scholar John Ikenberry attributes U.S. hegemony in part to what he says are commitments and self-restraint that the United States established through the creation of international institutions (such as the United Nations, International Monetary Fund, World Bank, and World Trade Organization). Constructivist scholar Martha Finnemore argues that legitimation and institutionalization are key components of unipolarity.

Sociology
Academics have argued that in the praxis of hegemony, imperial dominance is established by means of cultural imperialism, whereby the leader state (hegemon) dictates the internal politics and the societal character of the subordinate states that constitute the hegemonic sphere of influence, either by an internal, sponsored government or by an external, installed government. The imposition of the hegemon's way of life—an imperial lingua franca and bureaucracies (social, economic, educational, governing)—transforms the concrete imperialism of direct military domination into the abstract power of the status quo, indirect imperial domination. J. Brutt-Griffler, a critic of this view, has described it as "deeply condescending" and "treats people ... as blank slates on which global capitalism's moving finger writes its message, leaving behind another cultural automaton as it moves on."

Culturally, hegemony also is established by means of language, specifically the imposed lingua franca of the hegemon (leader state), which then is the official source of information for the people of the society of the sub-ordinate state. Writing on language and power, Andrea Mayr says, "As a practice of power, hegemony operates largely through language." In contemporary society, an example of the use of language in this way is in the way Western countries set up educational systems in African countries mediated by Western languages.

Suggested examples of cultural imperialism include the latter-stage Spanish, French colonial empires and British Empires, the 19th- and 20th-century Reichs of unified Germany (1871–1945), and by the end of the 20th century, the United States.

Media studies
Adopted from the work of Gramsci and Stuart Hall, hegemony with respect to media studies refers to individuals or concepts that become most dominant in a culture. Building on Gramsci's ideas, Hall stated that the media is a critical institution for furthering or inhibiting hegemony.

title: Hegemony


text:
Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer $p$ that are relatively prime to $n$. It is written using the Greek letter phi as $$\varphi(n)$$ or $$\phi(n)$$, and may also be called Euler's phi function. In other words, it is the number of integers $n$ in the range $φ(n)$ for which the greatest common divisor $φ(p)$ is equal to 1. The integers $k$ of this form are sometimes referred to as totatives of $k$.

For example, the totatives of $p − 1.$ are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since $1 ≤ k ≤ n$ and $gcd(n, k)$. Therefore, $n = 9$. As another example, $gcd(9, 3) = gcd(9, 6) = 3$ since for $gcd(9, 9) = 9$ the only integer in the range from 1 to $n$ is 1 itself, and $φ(9) = 6$.

Euler's totient function is a multiplicative function, meaning that if two numbers $n$ and $m$ are relatively prime, then $φ(1) = 1$. This function gives the order of the multiplicative group of integers modulo $n$ (the group of units of the ring $$\Z/n\Z$$). It is also used for defining the RSA encryption system.

History, terminology, and notation
Leonhard Euler introduced the function in 1763. However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter $n$ to denote it: he wrote $n = 1$ for "the multitude of numbers less than $n$, and which have no common divisor with it". This definition varies from the current definition for the totient function at $gcd(1, 1) = 1$ but is otherwise the same. The now-standard notation $φ(mn) = φ(m)φ(n)$ comes from Gauss's 1801 treatise Disquisitiones Arithmeticae, although Gauss did not use parentheses around the argument and wrote $πD$. Thus, it is often called Euler's phi function or simply the phi function.

In 1879, J. J. Sylvester coined the term totient for this function, so it is also referred to as Euler's totient function, the Euler totient, or Euler's totient. Jordan's totient is a generalization of Euler's.

The cototient of $N$ is defined as $D = 1$. It counts the number of positive integers less than or equal to $N$ that have at least one prime factor in common with $π$.

Computing Euler's totient function
There are several formulae for computing $φ(n)$.

Euler's product formula
It states
 * $$\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),$$

where the product is over the distinct prime numbers dividing $D$. (For notation, see Arithmetical function.)

An equivalent formulation is $$\varphi(n) = p_1^{k_1-1}(p_1{-}1)\,p_2^{k_2-1}(p_2{-}1)\cdots p_r^{k_r-1}(p_r{-}1),$$ where $$n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$$ is the prime factorization of $$n$$ (that is, $$p_1, p_2,\ldots,p_r$$ are distinct prime numbers).

The proof of these formulae depends on two important facts.

Phi is a multiplicative function
This means that if $ϕ(n)$, then $φ(A)$. Proof outline: Let $n$, $n$, $n$ be the sets of positive integers which are coprime to and less than $n$, $A$, $B$, respectively, so that $φA$, etc. Then there is a bijection between $n − φ(n)$ and $C$ by the Chinese remainder theorem.

Value of phi for a prime power argument
If $m$ is prime and $φ(n)$, then

 * $$\varphi \left(p^k\right) = p^k-p^{k-1} = p^{k-1}(p-1) = p^k \left( 1 - \tfrac{1}{p} \right).$$

Proof: Since $n$ is a prime number, the only possible values of $gcd(m, n) = 1$ are $φ(m) φ(n) = φ(mn)$, and the only way to have $|A| = φ(m)$ is if $mn$ is a multiple of $C$, that is, $A × B$, and there are $k ≥ 1$ such multiples not greater than $gcd(p^{k}, m)$. Therefore, the other $1, p, p^{2}, ..., p^{k}$ numbers are all relatively prime to $gcd(p^{k}, m) > 1$.

Proof of Euler's product formula
The fundamental theorem of arithmetic states that if $m ∈ \{1=p, 2p, 3p, ..., p^{k − 1}p = p^{k}\}$ there is a unique expression $$n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, $$ where $p^{k − 1}$ are prime numbers and each $p^{k}$. (The case $p^{k} − p^{k − 1}$ corresponds to the empty product.) Repeatedly using the multiplicative property of $p$ and the formula for $p^{k}$ gives

 * $$\begin{array} {rcl}

\varphi(n)&=& \varphi(p_1^{k_1})\, \varphi(p_2^{k_2}) \cdots\varphi(p_r^{k_r})\\[.1em] &=& p_1^{k_1} \left(1- \frac{1}{p_1} \right) p_2^{k_2} \left(1- \frac{1}{p_2} \right) \cdots p_r^{k_r}\left(1- \frac{1}{p_r} \right)\\[.1em] &=& p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \left(1- \frac{1}{p_1} \right) \left(1- \frac{1}{p_2} \right) \cdots \left(1- \frac{1}{p_r} \right)\\[.1em] &=&n \left(1- \frac{1}{p_1} \right)\left(1- \frac{1}{p_2} \right) \cdots\left(1- \frac{1}{p_r} \right). \end{array}$$

This gives both versions of Euler's product formula.

An alternative proof that does not require the multiplicative property instead uses the inclusion-exclusion principle applied to the set $$\{1,2,\ldots,n\}$$, excluding the sets of integers divisible by the prime divisors.

Example

 * $$\varphi(20)=\varphi(2^2 5)=20\,(1-\tfrac12)\,(1-\tfrac15)

=20\cdot\tfrac12\cdot\tfrac45=8.$$

In words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.

The alternative formula uses only integers:$$\varphi(20) = \varphi(2^2 5^1)= 2^{2-1}(2{-}1)\,5^{1-1}(5{-}1) = 2\cdot 1\cdot 1\cdot 4 = 8.$$

Fourier transform
The totient is the discrete Fourier transform of the gcd, evaluated at 1. Let

 * $$ \mathcal{F} \{ \mathbf{x} \}[m] = \sum\limits_{k=1}^n x_k \cdot e^{{-2\pi i}\frac{mk}{n}}$$

where $n > 1$ for $p_{1} < p_{2} < ... < p_{r}$. Then

 * $$\varphi (n) = \mathcal{F} \{ \mathbf{x} \}[1] = \sum\limits_{k=1}^n \gcd(k,n) e^{-2\pi i\frac{k}{n}}.$$

The real part of this formula is

 * $$\varphi (n)=\sum\limits_{k=1}^n \gcd(k,n) \cos {\tfrac{2\pi k}{n}}

.$$

For example, using $$\cos\tfrac{\pi}5 = \tfrac{\sqrt 5+1}4 $$ and $$\cos\tfrac{2\pi}5 = \tfrac{\sqrt 5-1}4 $$:$$\begin{array}{rcl} \varphi(10) &=& \gcd(1,10)\cos\tfrac{2\pi}{10} + \gcd(2,10)\cos\tfrac{4\pi}{10} + \gcd(3,10)\cos\tfrac{6\pi}{10}+\cdots+\gcd(10,10)\cos\tfrac{20\pi}{10}\\ &=& 1\cdot(\tfrac{\sqrt5+1}4) + 2\cdot(\tfrac{\sqrt5-1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(-\tfrac{\sqrt5+1}4) + 5\cdot (-1) \\ && +\ 2\cdot(-\tfrac{\sqrt5+1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(\tfrac{\sqrt5-1}4) + 1\cdot(\tfrac{\sqrt5+1}4) + 10 \cdot (1) \\ &=& 4 . \end{array} $$Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of $p$. However, it does involve the calculation of the greatest common divisor of $m$ and every positive integer less than $p$, which suffices to provide the factorization anyway.

Divisor sum
The property established by Gauss, that

 * $$\sum_{d\mid n}\varphi(d)=n,$$

where the sum is over all positive divisors $φ$ of $n$, can be proven in several ways. (See Arithmetical function for notational conventions.)

One proof is to note that $k_{i} ≥ 1$ is also equal to the number of possible generators of the cyclic group $n = 1$ ; specifically, if $φ(p^{k})$ with $x_{k} = gcd(k,n)$, then $k ∈ {1, ..., n}$ is a generator for every $n$ coprime to $n$. Since every element of $φ(d)$ generates a cyclic subgroup, and each subgroup $C_{d}$ is generated by precisely $C_{d} = ⟨g⟩$ elements of $g^{d} = 1$, the formula follows. Equivalently, the formula can be derived by the same argument applied to the multiplicative group of the $d$th roots of unity and the primitive $n$th roots of unity.

The formula can also be derived from elementary arithmetic. For example, let $g^{k}$ and consider the positive fractions up to 1 with denominator 20:

\tfrac{ 1}{20},\,\tfrac{ 2}{20},\,\tfrac{ 3}{20},\,\tfrac{ 4}{20},\, \tfrac{ 5}{20},\,\tfrac{ 6}{20},\,\tfrac{ 7}{20},\,\tfrac{ 8}{20},\, \tfrac{ 9}{20},\,\tfrac{10}{20},\,\tfrac{11}{20},\,\tfrac{12}{20},\, \tfrac{13}{20},\,\tfrac{14}{20},\,\tfrac{15}{20},\,\tfrac{16}{20},\, \tfrac{17}{20},\,\tfrac{18}{20},\,\tfrac{19}{20},\,\tfrac{20}{20}. $$

Put them into lowest terms:

\tfrac{ 1}{20},\,\tfrac{ 1}{10},\,\tfrac{ 3}{20},\,\tfrac{ 1}{ 5},\, \tfrac{ 1}{ 4},\,\tfrac{ 3}{10},\,\tfrac{ 7}{20},\,\tfrac{ 2}{ 5},\, \tfrac{ 9}{20},\,\tfrac{ 1}{ 2},\,\tfrac{11}{20},\,\tfrac{ 3}{ 5},\, \tfrac{13}{20},\,\tfrac{ 7}{10},\,\tfrac{ 3}{ 4},\,\tfrac{ 4}{ 5},\, \tfrac{17}{20},\,\tfrac{ 9}{10},\,\tfrac{19}{20},\,\tfrac{1}{1} $$

These twenty fractions are all the positive $k$ ≤ 1 whose denominators are the divisors $C_{n}$. The fractions with 20 as denominator are those with numerators relatively prime to 20, namely $d$, $n$, $d$, $k⁄d$, $1⁄20$, $3⁄20$, $7⁄20$, $9⁄20$; by definition this is $C_{d} ⊆ C_{n}$ fractions. Similarly, there are $φ(d)$ fractions with denominator 10, and $C_{n}$ fractions with denominator 5, etc. Thus the set of twenty fractions is split into subsets of size $n = 20$ for each $d = 1, 2, 4, 5, 10, 20$ dividing 20. A similar argument applies for any n.

Möbius inversion applied to the divisor sum formula gives
 * $$ \varphi(n) = \sum_{d\mid n} \mu\left( d \right) \cdot \frac{n}{d} = n\sum_{d\mid n} \frac{\mu (d)}{d},$$

where $11⁄20$ is the Möbius function, the multiplicative function defined by $$\mu(p) = -1$$ and $$ \mu(p^k) = 0$$ for each prime $φ(20)$ and $φ(10)$. This formula may also be derived from the product formula by multiplying out $ \prod_{p\mid n} (1 - \frac{1}{p}) $ to get $ \sum_{d \mid n} \frac{\mu (d)}{d}. $

An example:$$ \begin{align} \varphi(20) &= \mu(1)\cdot 20 + \mu(2)\cdot 10 +\mu(4)\cdot 5 +\mu(5)\cdot 4 + \mu(10)\cdot 2+\mu(20)\cdot 1\\[.5em] &= 1\cdot 20 - 1\cdot 10 + 0\cdot 5 - 1\cdot 4 + 1\cdot 2 + 0\cdot 1 = 8. \end{align} $$

Some values
The first 100 values are shown in the table and graph below:

 * {| class="wikitable" style="text-align: right"

! + ! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 ! 0 ! 10 ! 20 ! 30 ! 40 ! 50 ! 60 ! 70 ! 80 ! 90
 * +$φ(5)$ for $φ(d)$
 * 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4
 * 10 || 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8
 * 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8
 * 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16
 * 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20
 * 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16
 * 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24
 * 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32
 * 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24
 * 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 || 40
 * }

In the graph at right the top line $d$ is an upper bound valid for all $13⁄20$ other than one, and attained if and only if $17⁄20$ is a prime number. A simple lower bound is $$\varphi(n) \ge \sqrt{n/2} $$, which is rather loose: in fact, the lower limit of the graph is proportional to $p$.

Euler's theorem
This states that if $19⁄20$ and $μ$ are relatively prime then

 * $$ a^{\varphi(n)} \equiv 1\mod n.$$

The special case where $n$ is prime is known as Fermat's little theorem.

This follows from Lagrange's theorem and the fact that $k ≥ 2$ is the order of the multiplicative group of integers modulo $n$.

The RSA cryptosystem is based on this theorem: it implies that the inverse of the function $φ(n)$, where $a$ is the (public) encryption exponent, is the function $1 ≤ n ≤ 100$, where $n$, the (private) decryption exponent, is the multiplicative inverse of $n$ modulo $y = n − 1$. The difficulty of computing $n⁄log log n$ without knowing the factorization of $n$ is thus the difficulty of computing $e$: this is known as the RSA problem which can be solved by factoring $d$. The owner of the private key knows the factorization, since an RSA private key is constructed by choosing $e$ as the product of two (randomly chosen) large primes $n$ and $d$. Only $n$ is publicly disclosed, and given the difficulty to factor large numbers we have the guarantee that no one else knows the factorization.

Other formulae
 $$a\mid b \implies \varphi(a)\mid\varphi(b)$$ $$ m \mid \varphi(a^m-1)$$ $$\varphi(mn) = \varphi(m)\varphi(n)\cdot\frac{d}{\varphi(d)} \quad\text{where }d = \operatorname{gcd}(m,n)$$ In particular: 2\varphi(m) &\text{ if } m \text{ is even} \\ \varphi(m) &\text{ if } m \text{ is odd} \end{cases}$$ $$\varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)$$ Compare this to the formula $\operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n$  (see least common multiple).  $φ(n)$ is even for $a ↦ a^{e} mod n$. Moreover, if $n$ has $p$ distinct odd prime factors, $b ↦ b^{d} mod n$   For any $φ(n)$ and $φ(n)$ such that $φ(n)$ there exists an $n ≥ 3$ such that $2^{r} | φ(n)$. $$\frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}$$ where $a > 1$ is the radical of $q$ (the product of all distinct primes dividing $n$).  $$\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}$$
$$\sum_{1\le k\le n-1 \atop gcd(k,n)=1}\!\!k = \tfrac12 n\varphi(n) \quad \text{for }n>1$$

$$\sum_{k=1}^n\varphi(k) = \tfrac12 \left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right) =\frac3{\pi^2}n^2+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right)$$ ( cited in )

 * $$\varphi(2m) = \begin{cases}
 * $$\varphi\left(n^m\right) = n^{m-1}\varphi(n)$$

$$\sum_{k=1}^n\varphi(k) =\frac3{\pi^2}n^2+O\left(n(\log n)^\frac23(\log\log n)^\frac13\right) $$ [Liu (2016)]

$$\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+O\left((\log n)^\frac23(\log\log n)^\frac43\right)$$

$$\sum_{k=1}^n\frac{k}{\varphi(k)} = \frac{315\,\zeta(3)}{2\pi^4}n-\frac{\log n}2+O\left((\log n)^\frac23\right)$$

$$\sum_{k=1}^n\frac{1}{\varphi(k)} = \frac{315\,\zeta(3)}{2\pi^4}\left(\log n+\gamma-\sum_{p\text{ prime}}\frac{\log p}{p^2-p+1}\right)+O\left(\frac{(\log n)^\frac23}n\right)$$ (where $n$ is the Euler–Mascheroni constant).

Menon's identity
In 1965 P. Kesava Menon proved
 * $$\sum_{\stackrel{1\le k\le n}{ \gcd(k,n)=1}} \!\!\!\! \gcd(k-1,n)=\varphi(n)d(n),$$

where $n > 6$ is the number of divisors of $r$.

Divisibility by any fixed positive integer
The following property, which is part of the « folklore » (i.e., apparently unpublished as a specific result: see the introduction of this article in which it is stated as having « long been known ») has important consequences. For instance it rules out uniform distribution of the values of $$\varphi(n)$$ in the arithmetic progressions modulo $$q$$ for any integer $$q>1$$.

 * For every fixed positive integer $$q$$, the relation $$q|\varphi(n)$$ holds for almost all $$n$$, meaning for all but $$o(x)$$ values of $$n\le x$$ as $$x\rightarrow\infty$$.

This is an elementary consequence of the fact that the sum of the reciprocals of the primes congruent to 1 modulo $$q$$ diverges, which itself is a corollary of the proof of Dirichlet's theorem on arithmetic progressions.

Generating functions
The Dirichlet series for $4 ∤ n$ may be written in terms of the Riemann zeta function as:
 * $$\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}$$

where the left-hand side converges for $$\Re (s)>2$$.

The Lambert series generating function is

 * $$\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}$$

which converges for $l ≥ 2n$.

Both of these are proved by elementary series manipulations and the formulae for $l | φ(a^{n} − 1)$.

Growth rate
In the words of Hardy & Wright, the order of $rad(n)$ is "always 'nearly $n$'."

First

 * $$\lim\sup \frac{\varphi(n)}{n}= 1,$$

but as n goes to infinity, for all $d(n) = σ_{0}(n)$

 * $$\frac{\varphi(n)}{n^{1-\delta}}\rightarrow\infty.$$

These two formulae can be proved by using little more than the formulae for $φ(n)$ and the divisor sum function $|q| < 1$.

In fact, during the proof of the second formula, the inequality

 * $$\frac {6}{\pi^2} < \frac{\varphi(n) \sigma(n)}{n^2} < 1,$$

true for $φ(n)$, is proved.

We also have

 * $$\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma}.$$

Here $n$ is Euler's constant, $φ(n)$, so $δ > 0$ and $φ(n)$.

Proving this does not quite require the prime number theorem. Since $σ(n)$ goes to infinity, this formula shows that

 * $$\lim\inf\frac{\varphi(n)}{n}= 0.$$

In fact, more is true.

 * $$\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} \quad\text{for } n>2$$

and

 * $$\varphi(n) < \frac {n} {e^{ \gamma}\log \log n} \quad\text{for infinitely many } n.$$

The second inequality was shown by Jean-Louis Nicolas. Ribenboim says "The method of proof is interesting, in that the inequality is shown first under the assumption that the Riemann hypothesis is true, secondly under the contrary assumption."

For the average order, we have

 * $$\varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right) \quad\text{as }n\rightarrow\infty,$$

due to Arnold Walfisz, its proof exploiting estimates on exponential sums due to I. M. Vinogradov and N. M. Korobov. By a combination of van der Corput's and Vinogradov's methods, H.-Q. Liu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) improved the error term to

O\left(n(\log n)^\frac23(\log\log n)^\frac13\right) $$ (this is currently the best known estimate of this type). The "Big $γ$" stands for a quantity that is bounded by a constant times the function of $n$ inside the parentheses (which is small compared to $n > 1$).

This result can be used to prove that the probability of two randomly chosen numbers being relatively prime is $n$.

Ratio of consecutive values
In 1950 Somayajulu proved

 * $$\begin{align}

\lim\inf \frac{\varphi(n+1)}{\varphi(n)}&= 0 \quad\text{and} \\[5px] \lim\sup \frac{\varphi(n+1)}{\varphi(n)}&= \infty. \end{align}$$

In 1954 Schinzel and Sierpiński strengthened this, proving that the set

 * $$\left\{\frac{\varphi(n+1)}{\varphi(n)},\;\;n = 1,2,\ldots\right\}$$

is dense in the positive real numbers. They also proved that the set

 * $$\left\{\frac{\varphi(n)}{n},\;\;n = 1,2,\ldots\right\}$$

is dense in the interval (0,1).

Totient numbers
A totient number is a value of Euler's totient function: that is, an $γ$ for which there is at least one $O$ for which $γ = 0.577215665...$. The valency or multiplicity of a totient number $n$ is the number of solutions to this equation. A nontotient is a natural number which is not a totient number. Every odd integer exceeding 1 is trivially a nontotient. There are also infinitely many even nontotients, and indeed every positive integer has a multiple which is an even nontotient.

The number of totient numbers up to a given limit $6⁄\pi^{2}$ is

 * $$\frac{x}{\log x}e^{ \big(C+o(1)\big)(\log\log\log x)^2 } $$

for a constant $e^{γ} = 1.7810724...$.

If counted accordingly to multiplicity, the number of totient numbers up to a given limit $m$ is

 * $$\Big\vert\{ n : \varphi(n) \le x \}\Big\vert = \frac{\zeta(2)\zeta(3)}{\zeta(6)} \cdot x + R(x)$$

where the error term $n$ is of order at most $e^{−γ} = 0.56145948...$ for any positive $m$.

It is known that the multiplicity of $x$ exceeds $log log n$ infinitely often for any $n^{2}$.

Ford's theorem
proved that for every integer $φ(n) = m$ there is a totient number $x$ of multiplicity $R$: that is, for which the equation $C = 0.8178146...$ has exactly $k$ solutions; this result had previously been conjectured by Wacław Sierpiński, and it had been obtained as a consequence of Schinzel's hypothesis H. Indeed, each multiplicity that occurs, does so infinitely often.

However, no number $m$ is known with multiplicity $x⁄(log x)^{k}$. Carmichael's totient function conjecture is the statement that there is no such $m$.

Perfect totient numbers
A perfect totient number is an integer that is equal to the sum of its iterated totients. That is, we apply the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of numbers; if the sum equals n, then n is a perfect totient number.

Cyclotomy
In the last section of the Disquisitiones Gauss proves that a regular $k$-gon can be constructed with straightedge and compass if $m^{δ}$ is a power of 2. If $k$ is a power of an odd prime number the formula for the totient says its totient can be a power of two only if $m$ is a first power and $δ < 0.55655$ is a power of 2. The primes that are one more than a power of 2 are called Fermat primes, and only five are known: 3, 5, 17, 257, and 65537. Fermat and Gauss knew of these. Nobody has been able to prove whether there are any more.

Thus, a regular $m$-gon has a straightedge-and-compass construction if n is a product of distinct Fermat primes and any power of 2. The first few such $n$ are
 * 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,....

The RSA cryptosystem
Setting up an RSA system involves choosing large prime numbers $n$ and $n$, computing $k ≥ 2$ and $φ(n) = m$, and finding two numbers $n$ and $n$ such that $k = 1$. The numbers $n$ and $n$ (the "encryption key") are released to the public, and $n$ (the "decryption key") is kept private.

A message, represented by an integer $n$, where $φ(n)$, is encrypted by computing $n − 1$.

It is decrypted by computing $n = pq$. Euler's Theorem can be used to show that if $k = φ(n)$, then $ed ≡ 1 (mod k)$.

The security of an RSA system would be compromised if the number $p$ could be efficiently factored or if $0 < m < n$ could be efficiently computed without factoring $q$.

Lehmer's conjecture
If $e$ is prime, then $S = m^{e} (mod n)$. In 1932 D. H. Lehmer asked if there are any composite numbers $d$ such that $t = S^{d} (mod n)$ divides $0 < t < n$. None are known.

In 1933 he proved that if any such $n$ exists, it must be odd, square-free, and divisible by at least seven primes (i.e. $t = m$). In 1980 Cohen and Hagis proved that $φ(n)$ and that $φ(p) = p − 1$. Further, Hagis showed that if 3 divides $e$ then $φ(n)$ and $n − 1$.

Carmichael's conjecture
This states that there is no number $d$ with the property that for all other numbers $m$, $ω(n) ≥ 7$, $n > 10^{20}$. See Ford's theorem above.

As stated in the main article, if there is a single counterexample to this conjecture, there must be infinitely many counterexamples, and the smallest one has at least ten billion digits in base 10.

Riemann hypothesis
The Riemann hypothesis is true if and only if the inequality
 * $$\frac{n}{\varphi (n)}<e^\gamma \log\log n+\frac{e^\gamma (4+\gamma-\log 4\pi)}{\sqrt{\log n}}$$

is true for all $ω(n) ≥ 14$ where $n$ is Euler's constant and $φ(n)$ is the product of the first $n − 1$ primes.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Euler's totient function


text:
Fermat's little theorem

In number theory, Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^{p} − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as $$a^p \equiv a \pmod p.$$

For example, if $a = 2$ and $p = 7$, then $2^{7} = 128$, and $128 − 2 = 126 = 7 × 18$ is an integer multiple of $7$.

If $a$ is not divisible by $p$, that is, if $a$ is coprime to $p$, then Fermat's little theorem is equivalent to the statement that $a^{p − 1} − 1$ is an integer multiple of $p$, or in symbols: $$a^{p-1} \equiv 1 \pmod p.$$

For example, if $a = 2$ and $p = 7$, then $2^{6} = 64$, and $64 − 1 = 63 = 7 × 9$ is a multiple of $7$.

Fermat's little theorem is the basis for the Fermat primality test and is one of the fundamental results of elementary number theory. The theorem is named after Pierre de Fermat, who stated it in 1640. It is called the "little theorem" to distinguish it from Fermat's Last Theorem.

History
Pierre de Fermat first stated the theorem in a letter dated October 18, 1640, to his friend and confidant Frénicle de Bessy. His formulation is equivalent to the following:

If $p$ is a prime and $a$ is any integer not divisible by $p$, then $a^{ p − 1} − 1$ is divisible by $p$.

Fermat's original statement was Tout nombre premier mesure infailliblement une des puissances $-1$ de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné $-1$; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question. This may be translated, with explanations and formulas added in brackets for easier understanding, as: Every prime number [$p$] divides necessarily one of the powers minus one of any [geometric] progression [$a, a^{2}, a^{3}, …$] [that is, there exists $t$ such that $p$ divides $a^{t} – 1$], and the exponent of this power [$t$] divides the given prime minus one [divides $p – 1$]. After one has found the first power [$t$] that satisfies the question, all those whose exponents are multiples of the exponent of the first one satisfy similarly the question [that is, all multiples of the first $t$ have the same property].

Fermat did not consider the case where $a$ is a multiple of $p$ nor prove his assertion, only stating: "Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long." "(And this proposition is generally true for all series [sic] and for all prime numbers; I would send you a demonstration of it, if I did not fear going on for too long.)"

Euler provided the first published proof in 1736, in a paper titled "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" (in English: "Demonstration of Certain Theorems Concerning Prime Numbers") in the Proceedings of the St. Petersburg Academy, but Leibniz had given virtually the same proof in an unpublished manuscript from sometime before 1683.

The term "Fermat's little theorem" was probably first used in print in 1913 in Zahlentheorie by Kurt Hensel:

"Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist."

"(There is a fundamental theorem holding in every finite group, usually called Fermat's little theorem because Fermat was the first to have proved a very special part of it.)"

An early use in English occurs in A.A. Albert's Modern Higher Algebra (1937), which refers to "the so-called 'little' Fermat theorem" on page 206.

Further history
Some mathematicians independently made the related hypothesis (sometimes incorrectly called the Chinese hypothesis) that $2^{p} ≡ 2 (mod p)$ if and only if $p$ is prime. Indeed, the "if" part is true, and it is a special case of Fermat's little theorem. However, the "only if" part is false: For example, $2^{341} ≡ 2 (mod 341)$, but 341 = 11 × 31 is a pseudoprime to base 2. See below.

Proofs
Several proofs of Fermat's little theorem are known. It is frequently proved as a corollary of Euler's theorem.

Generalizations
Euler's theorem is a generalization of Fermat's little theorem: For any modulus $n$ and any integer $a$ coprime to $n$, one has

$$a^{\varphi (n)} \equiv 1 \pmod n,$$

where $φ(n)$ denotes Euler's totient function (which counts the integers from 1 to $n$ that are coprime to $n$). Fermat's little theorem is indeed a special case, because if $n$ is a prime number, then $φ(n) = n − 1$.

A corollary of Euler's theorem is: For every positive integer $n$, if the integer $a$ is coprime with $n$, then $$x \equiv y \pmod{\varphi(n)}\quad\text{implies}\quad a^x \equiv a^y \pmod n, $$ for any integers $x$ and $y$. This follows from Euler's theorem, since, if $$x \equiv y \pmod{\varphi(n)}$$, then $x = y + kφ(n)$ for some integer $k$, and one has $$a^x = a^{y + \varphi(n)k} = a^y (a^{\varphi(n)})^k \equiv a^y 1^k \equiv a^y \pmod n.$$

If $n$ is prime, this is also a corollary of Fermat's little theorem. This is widely used in modular arithmetic, because this allows reducing modular exponentiation with large exponents to exponents smaller than $n$.

Euler's theorem is used with $n$ not prime in public-key cryptography, specifically in the RSA cryptosystem, typically in the following way: if $$y=x^e\pmod n,$$ retrieving $x$ from the values of $y$, $e$ and $n$ is easy if one knows $φ(n)$. In fact, the extended Euclidean algorithm allows computing the modular inverse of $y$ modulo $φ(n)$, that is, the integer $n$ such that $$ef\equiv 1\pmod{\varphi(n)}.$$ It follows that $$x\equiv x^{ef}\equiv (x^e)^f \equiv y^f \pmod n.$$

On the other hand, if $n = pq$ is the product of two distinct prime numbers, then $φ(n) = (p − 1)(q − 1)$. In this case, finding $n$ from $e$ and $f$ is as difficult as computing $φ(n)$ (this has not been proven, but no algorithm is known for computing $f$ without knowing $φ(n)$). Knowing only $n$, the computation of $φ(n)$ has essentially the same difficulty as the factorization of $e$, since $φ(n) = (p − 1)(q − 1)$, and conversely, the factors $f$ and $n$ are the (integer) solutions of the equation $x2 – (n − φ(n) + 1) x + n = 0$.

The basic idea of RSA cryptosystem is thus: If a message $n$ is encrypted as $y = x^{e} (mod n)$, using public values of $p$ and $q$, then, with the current knowledge, it cannot be decrypted without finding the (secret) factors $x$ and $n$ of $e$.

Fermat's little theorem is also related to the Carmichael function and Carmichael's theorem, as well as to Lagrange's theorem in group theory.

Converse
The converse of Fermat's little theorem is not generally true, as it fails for Carmichael numbers. However, a slightly stronger form of the theorem is true, and it is known as Lehmer's theorem. The theorem is as follows:

If there exists an integer $p$ such that $$ a^{p-1}\equiv 1\pmod p $$ and for all primes $q$ dividing $p − 1$ one has $$ a^{(p-1)/q}\not\equiv 1\pmod p, $$ then $n$ is prime.

This theorem forms the basis for the Lucas primality test, an important primality test, and Pratt's primality certificate.

Pseudoprimes
If $a$ and $q$ are coprime numbers such that $a^{p−1} − 1$ is divisible by $p$, then $a$ need not be prime. If it is not, then $p$ is called a (Fermat) pseudoprime to base $p$. The first pseudoprime to base 2 was found in 1820 by Pierre Frédéric Sarrus: 341 = 11 × 31.

A number $p$ that is a Fermat pseudoprime to base $p$ for every number $a$ coprime to $p$ is called a Carmichael number. Alternately, any number $a$ satisfying the equality $$\gcd\left(p, \sum_{a=1}^{p-1} a^{p-1}\right)=1$$ is either a prime or a Carmichael number.

Miller–Rabin primality test
The Miller–Rabin primality test uses the following extension of Fermat's little theorem: "If $a$ is an odd prime and $p − 1 = 2^{s}d$ with $s > 0$ and $p$ odd > 0, then for every $p$ coprime to $p$, either $a^{d} ≡ 1 (mod p)$ or there exists $d$ such that $0 ≤ r < s$ and $a^{2^{r}d} ≡ −1 (mod p)$."

This result may be deduced from Fermat's little theorem by the fact that, if $a$ is an odd prime, then the integers modulo $p$ form a finite field, in which 1 modulo $r$ has exactly two square roots, 1 and −1 modulo $p$.

Note that $a^{d} ≡ 1 (mod p)$ holds trivially for $a ≡ 1 (mod p)$, because the congruence relation is compatible with exponentiation. And $a^{d} = a^{2^{0}d} ≡ −1 (mod p)$ holds trivially for $a ≡ −1 (mod p)$ since $p$ is odd, for the same reason. That is why one usually chooses a random $p$ in the interval $1 < a < p − 1$.

The Miller–Rabin test uses this property in the following way: given an odd integer $p$ for which primality has to be tested, write $p − 1 = 2^{s}d$ with $s > 0$ and $d$ odd > 0, and choose a random $a$ such that $1 < a < p − 1$; then compute $b = a^{d} mod p$; if $p$ is not 1 nor −1, then square it repeatedly modulo $d$ until you get −1 or have squared $s − 1$ times. If $b ≠ 1$ and −1 has not been obtained by squaring, then $a$ is a composite and $b$ is a witness for the compositeness of $p$. Otherwise, $p$ is a strong probable prime to base a; that is, it may be prime or not. If $a$ is composite, the probability that the test declares it a strong probable prime anyway is at most $p$, in which case $p$ is a strong pseudoprime, and $p$ is a strong liar. Therefore after $1/4$ non-conclusive random tests, the probability that $p$ is composite is at most 4−k, and may thus be made as low as desired by increasing $a$.

In summary, the test either proves that a number is composite or asserts that it is prime with a probability of error that may be chosen as low as desired. The test is very simple to implement and computationally more efficient than all known deterministic tests. Therefore, it is generally used before starting a proof of primality.

title: Fermat's little theorem


text:
Talk:Fermat's little theorem

Proof?
I think it should be great to include a proof of the theorem in the article. If it is then sorry. — Preceding unsigned comment added by Santropedro1 (talk • contribs) 04:05, 14 June 2013 (UTC)

Division form section
I want to introduce the usage of $$p^k|(x^p-x)^k$$.Should it belongs to Fermat's little theorem?--Tttfffkkk (talk) 00:13, 22 September 2015 (UTC)

$$p|x^p-x \Rightarrow p^k|(x^p-x)^k$$

 * 1) $$\displaystyle x^{pk} \equiv \sum_{i=1}^k (-1)^{i-1} \binom{k}{i} x^{pk-(p-1)i} \pmod {p^k}$$
 * 2) $$\displaystyle x^{pk+(p-1)n} \equiv \sum_{i=1}^k (-1)^{i-1} \binom{n+i-1}{i-1} \binom{n+k}{k-i} x^{pk-(p-1)i} \pmod {p^k}$$

The related journal is written in Chinese.--Tttfffkkk (talk) 04:30, 23 September 2015 (UTC)

 * What you are describing here are direct computational applications of Fermat's little theorem (the first is no more than an application of the binomial theorem). The other applications mentioned in the article were notable mathematical results and I fail to see how these formulae would be considered notable. References written in other languages are not prohibited, but should be limited to material that is not available in English or of significant notability in its own right (neither of which would be true in this case). Also, this reference is a newly published (2015) primary source and the Wikipedia preference is for reliable secondary sources. I do not see how this addition could be improved to make it a reasonable contribution to this article. Bill Cherowitzo (talk) 19:00, 23 September 2015 (UTC)

 * Thanks for replying.Everyone would prefer using Euler's theorem than copying this long summation. The only advantage of this method is that the degree of divisor pk is lower than $$\varphi(p^k)$$.So that at least you can use this method after using Euler's theorem(If not,this long summation would be totally useless).You can make the degree much more lower by $$x(x+1)...(x+n-1)$$(reach to Kempner function),but the formula of remainder is too big.--Tttfffkkk (talk) 01:16, 24 September 2015 (UTC)

Translation
• Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

• (And this proposition is generally true for all series and for all prime numbers; the proof of which I would send to you, if I did not fear it being too long.)

I believe anyone familiar with Middle French & with English would think that "if I did not fear being too long" would be a better translation than the one proposed. However, the source of the translation offered is given as a reference. I don't know how to approach this from a Wikipedian point of view, and therefore I am reluctant to change it myself, but would still appreciate pointers as to what to do in a case like this. --66.185.60.38 (talk) 21:00, 16 January 2016 (UTC)

 * This is an interesting question! My French is not good enough to have an independent opinion about which of the two English translations is a closer approximation of the French original.  Here are my two cents:
 * I think that "the Wikipedian approach" (or really the approach of an encyclopedia) should be to follow reliable sources. Presumably the Ore book is generally reliable (though, maybe not for the quality of its French translations!) and presumably the quoted translation is actually what appears there (but I don't know, I don't have a copy), and in that case I think that this creates at least a small presumption in favor of following Ore's quote.
 * I think neither what is written already in the article nor the proposed alternative are exactly how I would phrase the given idea (in English); however, the proposed alternative sounds slightly less idiomatic to me. So, on grounds of what sounds good in English, I have a (very slight) preference for what is written.
 * I do not feel strongly about either point, obviously. And of course it would be good to check that we have actually reproduced the quote from Ore correctly.  If you would like other opinions (and if this comment doesn't attract them), possible places to ask would be the math project (which has many active editors) and the France project (which seems less active but is maybe more on point).  --JBL (talk) 15:56, 10 February 2016 (UTC)

 * Just to complicate matters somewhat, the quoted translation is not Ore's but rather the one given by Bergeron & Zhao. Ore's translation is not identical, but doesn't differ in any significant way. It is, "And this proposition is generally true for all series and all prime numbers. I would send you the demonstration, if I did not fear it being too long." This doesn't shed any light on the question at hand (and my French is also not good enough for me to have an opinion on that). However, Ore does supply a translation of another two paragraphs of the letter, and even my untrained eye can tell that he is much closer to the original than Bergeron & Zhao are. This leads me to question the Bergeron & Zhao source, which does not appear to be published. Bill Cherowitzo (talk) 18:06, 10 February 2016 (UTC)

 * A couple of additional thoughts. Ore would be considered a reliable source, but his translation is being questioned. To bring this up in the article would require a reliable source that translated it the other way. This is a well known letter and I am sure that there must be other translations out there somewhere. I would like to get 's take on this, he might find this interesting enough to help locate some. Secondly, I am hesitant to rely on the Bergeron & Zhao cite. This does not strike me as a professional translation. An historian would try to translate into a version of English that is more contemporary with Fermat, or at least recalling the flavor of Middle French, instead of the modernized prose that we find here. Also, having no sources mentioned, it is hard to determine if transcription errors from the handwritten letter occurred or not. My overall feeling is that this may have been a student project. Bill Cherowitzo (talk) 21:06, 10 February 2016 (UTC)

 * There's this translation, which to me is closer to the original, but is unfortunately not sourced: https://en.wikiquote.org/wiki/Pierre_de_Fermat
 * • And this proposition is generally true for all progressions and for all prime numbers; the proof of which I would send to you, if I were not afraid to be too long.    --66.185.60.38 (talk) 21:43, 10 February 2016 (UTC)

 * It actually is pretty identical to the translation offered here: http://www.personal.psu.edu/jxs23/courses/math035/fa11/handouts/24_fermats_little_theorem.pdf . Good enough for the main article? --66.185.60.38 (talk) 21:46, 10 February 2016 (UTC)

 * Course notes wouldn't really work here (course notes from a math history class might) and Sellers hedges by say "One translation could be ...". I have uncovered another wrinkle in this story. In a 2005 article on Fermat, there is a quote from A. Weil's math history book concerning a letter written to Mersenne by Fermat. The verbatim quote is "he would send [the proof] to Frenicle if he did not fear [it] being too long." I interpret this as indicating that Fermat used the same phrase in this letter as he did in the Frenicle letter. That Weil chose to throw in the "it" for clarification may mean that Fermat's use of the phrase could be idiosyncratic and he might not mean exactly what he wrote. Fermat is well known (according to his biographer) for not supplying proofs, especially in number theory, and he might just be using this as a stock phrase to cover his tracks. Only a Fermat scholar would be able able to clarify this. Bill Cherowitzo (talk) 00:23, 11 February 2016 (UTC)

 * Sorry, I am not good for finding sources. However I can explain why the disputed translation is faulty. Firstly, there is no reason for for translating "progressions" by "series": both words exist in French and in English, with the same meaning in both languages. Certainly, the modern meaning of "progression" is not exactly the same as it was at the time of Fermat, but this is not a reason for changing the word. Moreover, "progression" clearly refers to the geometric progression of the powers of a. In other words, the theorem says that the geometric progression of basis a is periodic modulo p, of period p – 1, for all a and all prime p. Thus translating "progression" by "series" is definitively a misinterpretation.
 * The "it" is also a misinterpretation, suggesting that it is the proof that is too long. It is Fermat itself (implicitly its letter) who could be too long. In French (old and new), it is common to say "je suis trop long" (I am too long) for "my speech or my letter is too long". I do not know if "I am too long" is understood in English in the same way. If yes, "if I did not fear being too long" would be a good translation. In the other case, I suggest something like "if I did not fear [my letter] being too long".
 * Also, "appréhendois" is not a past, but a subjunctive. Thus "if I would not fear" is probably a better translation. However, my knowledge of English grammar is not enough to be sure. D.Lazard (talk) 23:35, 10 February 2016 (UTC)

 * Thanks. We had an edit conflict as I was typing my response above. Being "too long" is quite understandable in English as it corresponds to the phrase, "being long-winded" (i.e., saying too much). Your response re-enforces my feeling about the Bergeron & Zhao translation, but still leaves me wondering about Ore's translation (assuming he translated it himself). Bill Cherowitzo (talk) 00:23, 11 February 2016 (UTC)

 * "if I were not afraid to be too long." actually uses the subjunctive form. That's one more thing I liked about the version I proposed a few hours ago, compared to the one currently used. --66.185.60.38 (talk) 23:59, 10 February 2016 (UTC)

 * As an afterthought, if the "[it]" in the quote I gave was put in by the author (Israel Kleiner) and did not appear in A. Weil's book, then I would be inclined to believe that Ore got it wrong. Unfortunately, I don't have access to this book to check ... but if someone does it is, A. Weil, Number Theory: An approach through History, from Hammurapi to Legendre, Birkhauser, 1984, page 56. We would still need a reliable source for the translation. Bill Cherowitzo (talk) 05:05, 11 February 2016 (UTC)

 * I was able to see what Weil wrote, and there is no "[it]" in his statement. Weil can certainly be considered an authority when it comes to Fermat (his criticism of a biography of Fermat is worth reading) and needless to say, his French (and Latin for that matter) are impeccable. I am now pretty sure that Ore's translation is in error, but we still need a reliable secondary source for the correct translation (as some Wikipedians are fond of saying, the truth itself is not sufficient, we need verifiability). Bill Cherowitzo (talk) 19:03, 11 February 2016 (UTC)
 * Weil can also certainly be considered an authority for translating mathematics from French to English, as he was a native French speaker, who spent a large part of his career in USA. D.Lazard (talk) 19:35, 11 February 2016 (UTC)

Around Fermat's citation
The discussion in the preceding section has pointed to me that the sentence before Fermat's citation was wrong. For fixing it, I had to quote original Fermat's statement of the theorem and to provide a translation. This shows undoubtedly that Fermat used "progression" for geometric progression, and thus translating "progression" by "series" is a blatant mistake, probably caused by the ignorance of mathematics by the original translator. Therefore I have replaced "series" by "progression" in Ore translation. Nevertheless I strongly support replacing the whole translation, as suggested in the preceding thread. D.Lazard (talk) 16:57, 20 February 2016 (UTC)

 * I have finally found a reliable secondary source which translates the final phrase as, "...; I would send you a demonstration of it, if I did not fear going on for too long." I will make the change in the article. There is however, one problem. This translation, and every other translation I have seen, uses " ... generally true for all series and for all prime ...". I clearly see that Fermat uses "progression" here, so I agree with you, but am at a loss as to why this appears so uniformly (other uses of "progression" in the letter are translated as "progression", so this seems to be intentional). The author of this translation (Michael Mahoney) was criticized by Weil for making some translation errors in a review of the book, but this does not explain the consistent use of "series" by other translators.Bill Cherowitzo (talk) 19:31, 20 February 2016 (UTC)
 * I cannot answer to your question, but I may guess something: most sentences, where "progression" appear, contain mathematical statements that give hints for the meaning of the word. But here, taking this sentence out of the context, a reader, who is unable to understand that Fermat's little theorem is related with geometric progressions, cannot understand the word, and thus uses the word of the common language that seems (wrongly) to make more sense. I guess that many readers have copied this mistake only because the preceding sentence, that states the theorem, is rarely cited (I agree that it is rather difficult to understand, for a modern mathematician). This leads naturally to the wrong presentation, in the preceding version of the article, of what Fermat did wrote D.Lazard (talk) 19:57, 20 February 2016 (UTC).

Miller-Rabin: k non-conclusive tests
The article claims that since each test would reveal a non-prime with probability 3/4, conducting enough random tests brings the probability of revealing a non-prime arbitrarily close to 1. That logic would be fine if there were infinitely many tests to choose from. But each test starts with choosing a number a between 1 and p, so there are fewer than p tests to choose from. Therefore, the best probability of revealing a non-prime is about 1 - (1/4)^p, not 1 as the article says. Admittedly in practice, we only need to use the primality test on large numbers, so the probability of revealing a non-prime with repeated tests is quite close to 1.

We should edit the incorrect statement. I haven't yet done so because I have yet to find an authoritative source. CautiousTiger (talk) 20:21, 1 January 2018 (UTC)
 * Miller–Rabin primality test says: "It can be shown that for any odd composite n, at least 3/4 of the bases a are witnesses for the compositeness of n". That's the reason for this in Fermat's little theorem: "If $p$ is not prime, the probability that this is proved by the test is higher than 1/4." It means that if you test 1/4 of all a without finding a witness then n is certain to be prime. Making this many tests would be extremely slow compared to other primality proving methods so it's not done in practice. PrimeHunter (talk) 23:25, 1 January 2018 (UTC)
 * Ah, thanks for clearing up my confusion. Should we delete this section of the talk page now? CautiousTiger (talk) 01:48, 2 January 2018 (UTC)
 * no, there is no reason not to leave it as-is. --JBL (talk) 02:16, 2 January 2018 (UTC)

Recent edits
Seems like we've had a misunderstanding about recent edits on this article; what exactly did you feel the need to revert? Armadillopteryxtalk 19:49, 8 March 2018 (UTC)
 * To address at least what was written in your edit summary: Prior to my edits, there were numerous equations, especially in the lede, that were written half in math mode and half in plaintext. Sizes of numbers and variables were different, spacing around operators was inconsistent, and it was overall pretty messy IMHO. I've made the presentation uniform by putting all equations into TeX. Also, I didn't make any modifications to gendered nouns, so I'm not quite sure what you meant by that. Look forward to chatting.

Armadillopteryxtalk 19:56, 8 March 2018 (UTC)
 * For the record, "confidante" can, in English, refer to either gender, while "confidant" is exclusively male. I'm not bothered if you prefer "confidant," though. Armadillopteryxtalk 20:13, 8 March 2018 (UTC)

 * Hi Armadillopteryx,
 * It is a perennial problem on Wikipedia that the math formatting options are not ideal. But this is also true of LaTeX: its font, sizing, and baseline do not typically match surrounding text (depending in part on choice of browser etc.), and it is particularly jarring (as compared with the mvar or math templates, or even just italicization) when single inline variables are placed in  tags.  Hopefully, there will eventually be a long-term solution that can be implemented consistently everywhere; until that time, doing large-scale formatting changes is at best not worth the effort.
 * In addition, you changed the masculine noun "confidant" into the feminine form "confidante" in a situation in which it referred to a man, and many of your other edits (removing the phrase "in modern terminology", including grammatical square brackets into a mathematical formula, replacing "It is called the "little theorem"" with "It is called Fermat's little theorem") strike me as clear dis-improvements. Added after edit conflict: you are obviously mis-reading the Miriam--Webster entry, it says nothing like what you claim.  If anything, you have it completely backwards.
 * On the LaTeX question we could certainly seek additional opinions at e.g. WT:WPM; about the other edits, I would be willing to discuss them one by one if you think I am lumping something good in unfairly.
 * JBL (talk) 20:22, 8 March 2018 (UTC)
 * Hi ,
 * It is also jarring to have equations that include variables and numbers that are inconsistently sized and spaced, and for that reason I find it preferable to put all math characters into TeX; otherwise we have inconsistency not only between lines, but also within equations. When there are already some math characters or equations in math mode in the prose, it is therefore most consistent to keep them all in the same mode so they at least appear the same as one another.
 * If you read the Merriam-Webster definition carefully, it lists confidant as the very definition of confidante, with the added information that it is especially (but not exclusively!) used to refer to a female confidant. But as I said above, since both are acceptable, I'm fine with confidant.
 * Since we're translating dated French into modern English, the qualifier "in modern terminology" is superfluous. It would be relevant if translating, for example, Old English to Modern English or Old French to Modern French.
 * I changed plaintext brackets to math brackets because the first (and last) bracketed characters were in math mode, and as I'm sure you're aware, plaintext brackets are a few font sizes smaller than the math ones and look too small when next to something in math mode.
 * Fermat's little theorem is never referred to as the little theorem. Have you seen that anywhere?
 * Respectfully, I disagree with each point you've said and feel the article is in worse shape now than after my edits, but I am happy to continue this conversation until we reach a solution we both like. Armadillopteryxtalk 20:38, 8 March 2018 (UTC)
 * Since I didn't mention it above, I'll also just clarify that I agree it could be useful to seek additional opinions about the LaTeX questions at WT:WPM, as it could benefit this and numerous other articles. Armadillopteryxtalk 21:47, 8 March 2018 (UTC)
 * I must agree with JBL, I do not find these edits to be an improvement. If this were a true LaTeX implementation, I would agree with the conversions, but as Joel has pointed out the in-line TeX does not really work well with the sans serif typeface of the prose, especially with alignment and font size. Your reaction to the little theorem is clearly over the top. No one, as far as I can tell, has called this the little theorem. The remark was put in to explain where little comes from and not to provide an alternate name.--Bill Cherowitzo (talk) 22:17, 8 March 2018 (UTC)
 * Hi, thanks for your reply. I'm certainly willing to further discuss the LaTeX question, as it does ultimately boil down to preference and doesn't have a strictly right or wrong answer. As far as the changes in prose, I maintain that my edits were improvements for the reasons I've outlined above (with the exception of confidant, which I've also said is fine as is). I know that the intention behind the "little theorem" remark was simply to distinguish it from Fermat's last theorem, but strictly speaking, the sentence as stated now is semantically incorrect, because it does state that the theorem is called "the little theorem." The intention is clear, but especially in a mathematical article I think we ought to be rigorous in what we say and not let things slide because one can see "what was meant." Armadillopteryxtalk 22:24, 8 March 2018 (UTC)
 * When I am writing a mathematical article for a mathematical audience, rigor is paramount, period. However, that is not what we are doing here, we are writing an encyclopedia for a general audience (with, hopefully, a modicum of mathematical sensibility). This requires different priorities, and rigor loses its primary place. The rigor, that we as mathematicians thrive on, is thoroughly off-putting for a general audience; and if you lose your audience, who exactly is it that you are writing for? I am not saying that we toss rigor in this kind of writing–when things get too sloppy I start red-penciling like a crazyman–but it has to be softened and we must let some things slide, especially if they are not crucial and the general meaning is clear.--Bill Cherowitzo (talk) 22:46, 8 March 2018 (UTC)
 * I agree with you that clarity and accessibility to the widest possible audience is paramount on Wikipedia. That is especially true for mathematical articles, to which young students often turn for help understanding what they've learned in class. In the case of this "little theorem" remark, which I'm sure we can all agree is extraordinarily minor in any case, I would still hold that my edit increases clarity, or at very least is neutral with respect to clarity. In cases like this, where there is not a trade-off between rigor and clarity, why let the rigor slip with no real benefit? I'm not going to get hung up on that particular detail of this article, but I responded to it earlier since both you and JBL commented on it.

 * Since we're on the subject of clarity, I would like to note that the mass revert done on my edits also removed several small changes in wording that I made specifically to make the material more readable and easier to grasp for less initiated readers. There were also some stylistic mistakes I fixed, for example one paragraph in French that is not italicized (as it should be per MOS:ITAL and as the other French text in the article already is).

 * I think we all share the desire for the prose to be high-quality and straightforward, and I'm glad we're talking about it here. Armadillopteryxtalk 22:56, 8 March 2018 (UTC)
 * I've put in some corrections in grammar, format and style, with a couple of clarity edits as well. If you would like to continue to discuss LaTeX here (or at WT:WPM, as JBL suggested), I would participate. If consensus on this article is to keep the TeX use to a minimum, though, I can respect that. Armadillopteryxtalk 22:27, 9 March 2018 (UTC)

 * The previous edits made it very difficult to preserve some of the good edits that you made. I am happy with these current edits. While there are a few edits that I don't think are necessary, these are all style issues that can go either way and I do not see anything that needs fixing. The LaTeX issue has been discussed for years and is a sore point shared by all the serious math editors. I'd suggest reading some of the archived discussions at WT:WPM dealing with it before trying to re-open that can of worms. --Bill Cherowitzo (talk) 00:18, 10 March 2018 (UTC)
 * Thanks, Bill. Guess I'll start digging through the archives :-D Armadillopteryxtalk 01:43, 10 March 2018 (UTC)

(ec) Ok, spring break has started; here is a complete list of the things I disagree with as between the current version and the one I last reverted to.
 * 1) I object to removing "in modern terminology": this phrase is important and should be restored.  The translated text is not simply a translation of Fermat from 17th century French to modern English; it is also (separately) translated from archaic mathematical terminology into modern mathematical terminology and notation.
 * 2) I object to most of the edits to said translation: the comma after "that is" and the replacement of "multiple" with "multiples" are improvements; the others change notation and punctuation that Fermat used and that are understandable and unobjectionable, which makes it harder to compare the original and the translation for no benefit.
 * 3) I don't care about "entitled" versus "titled", but the added comma in that sentence breaks the flow unnecessarily.
 * 4) You have changed one instance of "Theorem" to "theorem" inside a quote; that should be restored.
 * 5) In general it is not necessary to add "it" in a construction of the following form: "A is B, and [it] is also C", and in both cases you have done so I think it reads more poorly afterwards.

Two additional notes: about "the 'little theorem'" (which you have not changed after I objected even though I didn't explain; thank you): I agree with Bill that this phrasing emphasizes the key point being made in the sentence (why the adjective little is used) while the alternative obscures it. I also personally don't like using capital letters after colons, but I don't care so much that I have tried to find out if WP:MOS has a preference for one option over the other.

Finally, obviously this is not every change you made. Some of the remainder I am indifferent about, and some are clear improvements, and obviously I have not bothered to point out the good ones, leaving this comment with an overall negative tone. So, my apologies for that, and also for blanket-reverting earlier when I did not have the time to be more careful. --JBL (talk) 00:35, 10 March 2018 (UTC)
 * Thanks for your comment, and no worries about the tone. I'll respond to your points in order:

 * 1) I don't have a strong preference about this one. I think that even when referring to dated mathematical terminology, since that terminology is in a foreign language in this article, the "in modern terminology" comment won't help most readers (who probably don't speak French). But it also doesn't hurt (apart from making the sentence longer), so if you prefer to add it back, I'm okay with that.
 * 2) I changed "–1" to "minus one" because I feel it could be confusing to some readers that the entity being described (a power minus one) is half in prose and half in numerals. Especially since this isn't an official translation and we have included the original text for comparison (and since most readers of the English article will probably skip the French text), I think this edit improves clarity. But here as well, my preference is not strong, and if you want to restore the numerals, I won't complain. As for the "[divides $p – 1$]; and after ... " part, I broke this into two sentences since it isn't grammatical for the "and after ... " portion to follow a semicolon in English. I don't think it makes a tangible difference in the ease of comparing the two texts, either. Therefore, I would prefer to keep this as a new sentence in the translation.
 * 3) I think the comma improved the flow of the sentence, but as the sentence is grammatical both with and without it, my preference is again small.
 * 4) "Theorem" was capitalized in the original German because all nouns are capitalized in German, but that convention is not normally preserved when translating non-proper nouns into English. Note that in the same sentence, "group" and "part" were also capitalized in the original but are not capitalized in the translation.
 * 5) In sentences of the "A is B, and [it] is also C" form, the "it" and the comma go hand in hand. So both of the following are correct:
 * 6) "A is B, and it is also C."
 * 7) "A is B and is also C."
 * But the following (the way it was) is not correct: "A is B, and is also C."
 * If you don't like the flow of the sentences in this article with the added "it," how about the comma-free alternatives?
 * Indeed, the "if" part is true and is a special case of Fermat's little theorem.
 * However, a slightly stronger form of the theorem is true and is known as Lehmer's theorem.
 * I'm equally happy with these and the "comma–it" versions.
 * As for capital letters after colons, that's also a matter of preference. When a dependent clause is introduced after a colon, it must begin with a lowercase letter. However, when the clause after the colon is independent, either a capital or lowercase letter may be used, so I'm also fine with either option here.
 * How does this all sound to you? Armadillopteryxtalk 01:24, 10 March 2018 (UTC)

Caceres conjecture
I removed the conjecture, dated this month, as we can find a contradiction in Carmichael number. — Arthur Rubin (talk) 04:32, 15 May 2019 (UTC)

 * Thank you! I was in the process of removing it when you just barely beat me to it.  All the edits to insert it had no edit summary and the conjecture appears to be recent original research. — Anita5192 (talk) 04:47, 15 May 2019 (UTC)

Fermat's little theorem unravelled.
$$A,B,p,q,r$$ are whole number s.

p is a prime number.

Is $$A^{p-1}-1$$ divisible by $$p$$. $$\frac{A^{p-1}-1}{p}=?$$

$$\frac{A^{p-1}-1^{p-1}}{p}=\frac{A^{p-1}-B^{p-1}}{p}$$

$$\frac{A^{p-1}-B^{p-1}}{p}=\frac{(p+q)^{p-1}-(p+r)^{p-1}}{p}$$

$$\frac{A^{p-1}-1^{p-1}}{p}=\frac{(p+q)^{p-1}-\{p+(-p+1)\}^{p-1}}{p}$$

$$\frac{A^{p-1}-1}{p}=\frac{\sum_{k=0}^{p-1}\binom{p-1}{k}p^{p-1-k}q^k-\sum_{k=0}^{p-1}\binom{p-1}{k}p^{p-1-k}(-p+1)^k}{p}$$

$$\frac{A^{p-1}-1}{p}=\sum_{k=0}^{p-1}\binom{p-1}{k}p^{p-2-k}q^k-\sum_{k=0}^{p-1}\binom{p-1}{k}p^{p-2-k}(-p+1)^k$$

$$\frac{A^{p-1}-1}{p}=\sum_{k=0}^{p-1}\binom{p-1}{k}p^{p-2-k}\{q^k-(-p+1)^k\}$$

The following is worth mentioning..

$$\binom{p-1}{p-1}p^{p-2-(p-1)}\{q^{p-1}-(-p+1)^{p-1}\}= \frac{\binom{p-1}{p-1}\{q^{p-1}-(-p+1)^{p-1}\}}{p} $$

$$\{q^{p-1}-(-p+1)^{p-1}\} $$ is divisible by $$p $$.

Wim Coenen (talk) 18:03, 7 January 2023 (UTC)

Adding to Fermat's little theorem unravelled.
$$A,B,p,q$$ are whole numbers.

$$p$$ is a prime number.

$$A\neq qp$$

You choose a random number $$B$$.

Then there is always a number $$A=B+p$$

$$A=B+p$$

$$\frac{A^{p-1}-B^{p-1}}{p}=\frac{(B+p)^{p-1}-B^{p-1}}{p}$$

$$\frac{A^{p-1}-B^{p-1}}{p}= \frac{\textstyle\sum_{k=0}^{p-1} \displaystyle\tbinom{p-1}{k}{B^{p-1-k}p^k-B^{p-1}}}{p}$$

$$\frac{A^{p-1}-B^{p-1}}{p}= \frac{\textstyle\sum_{k=1}^{p-1} \displaystyle\tbinom{p-1}{k}{B^{p-1-k}p^k+B^{p1}-B^{p-1}}}{p}$$

$$\frac{A^{p-1}-B^{p-1}}{p}= \frac{\textstyle\sum_{k=1}^{p-1} \displaystyle\tbinom{p-1}{k}{B^{p-1-k}p^k}}{p}$$

$$\frac{A^{p-1}-B^{p-1}}{p}= \textstyle\sum_{k=1}^{p-1} \displaystyle\tbinom{p-1}{k}{B^{p-1-k}p^{k-1}}$$

$$A^{P-1}-B^{p-1}$$ is divisible by $$p$$.

Wim Coenen (talk) 19:36, 7 January 2023 (UTC)

title: Talk:Fermat's little theorem


text:
Minkowski's theorem

In mathematics, Minkowski's theorem is the statement that every convex set in $$\mathbb{R}^n$$ which is symmetric with respect to the origin and which has volume greater than $$2^n$$ contains a non-zero integer point (meaning a point in $$\Z^n$$ that is not the origin). The theorem was proved by Hermann Minkowski in 1889 and became the foundation of the branch of number theory called the geometry of numbers. It can be extended from the integers to any lattice $$L$$ and to any symmetric convex set with volume greater than $$2^n\,d(L)$$, where $$d(L)$$ denotes the covolume of the lattice (the absolute value of the determinant of any of its bases).

Formulation
Suppose that $^{2}$ is a lattice of determinant $L$ in the $d(L)$-dimensional real vector space $$\mathbb{R}^n$$ and $n$ is a convex subset of $$\mathbb{R}^n$$ that is symmetric with respect to the origin, meaning that if $S$ is in $x$ then $S$ is also in $−x$. Minkowski's theorem states that if the volume of $S$ is strictly greater than $S$, then $2^{n} d(L)$ must contain at least one lattice point other than the origin. (Since the set $S$ is symmetric, it would then contain at least three lattice points: the origin 0 and a pair of points $S$, where $± x$.)

Example
The simplest example of a lattice is the integer lattice $$\mathbb{Z}^n$$ of all points with integer coefficients; its determinant is 1. For $x ∈ L \ 0$, the theorem claims that a convex figure in the Euclidean plane symmetric about the origin and with area greater than 4 encloses at least one lattice point in addition to the origin. The area bound is sharp: if $n = 2$ is the interior of the square with vertices $S$ then $(±1, ±1)$ is symmetric and convex, and has area 4, but the only lattice point it contains is the origin. This example, showing that the bound of the theorem is sharp, generalizes to hypercubes in every dimension $S$.

Proof
The following argument proves Minkowski's theorem for the specific case of $$L = \mathbb{Z}^2.$$

Proof of the case: Consider the map
 * $$f: S \to \mathbb{R}^2/2L, \qquad (x,y) \mapsto (x \bmod 2, y \bmod 2)$$

Intuitively, this map cuts the plane into 2 by 2 squares, then stacks the squares on top of each other. Clearly $n$ has area less than or equal to 4, because this set lies within a 2 by 2 square. Assume for a contradiction that $f (S)$ could be injective, which means the pieces of $f$ cut out by the squares stack up in a non-overlapping way. Because $S$ is locally area-preserving, this non-overlapping property would make it area-preserving for all of $f$, so the area of $S$ would be the same as that of $f (S)$, which is greater than 4. That is not the case, so the assumption must be false: $S$ is not injective, meaning that there exist at least two distinct points $f$ in $p_{1}, p_{2}$ that are mapped by $S$ to the same point: $f$.

Because of the way $f (p_{1}) = f (p_{2})$ was defined, the only way that $f$ can equal $f (p_{1})$ is for $f (p_{2})$ to equal $p_{2}$ for some integers $p_{1} + (2i, 2j)$ and $i$, not both zero. That is, the coordinates of the two points differ by two even integers. Since $j$ is symmetric about the origin, $S$ is also a point in $−p_{1}$. Since $S$ is convex, the line segment between $S$ and $−p_{1}$ lies entirely in $p_{2}$, and in particular the midpoint of that segment lies in $S$. In other words,
 * $$\tfrac{1}{2}\left(-p_1 + p_2\right) = \tfrac{1}{2}\left(-p_1 + p_1 + (2i, 2j)\right) = (i, j)$$

is a point in $S$. But this point $S$ is an integer point, and is not the origin since $(i, j)$ and $i$ are not both zero. Therefore, $j$ contains a nonzero integer point.

Remarks:
 * The argument above proves the theorem that any set of volume >\!\det(L) contains two distinct points that differ by a lattice vector. This is a special case of Blichfeldt's theorem.
 * The argument above highlights that the term 2^n \det(L) is the covolume of the lattice 2L.
 * To obtain a proof for general lattices, it suffices to prove Minkowski's theorem only for ; this is because every full-rank lattice can be written as for some linear transformation B, and the properties of being convex and symmetric about the origin are preserved by linear transformations, while the covolume of  is |\!\det(B)| and volume of a body scales by exactly  under an application of B^{-1}.

Bounding the shortest vector
Minkowski's theorem gives an upper bound for the length of the shortest nonzero vector. This result has applications in lattice cryptography and number theory.

Theorem (Minkowski's bound on the shortest vector): Let $L$  be a lattice. Then there is a $x \in L \setminus \{0\}$ with $  \|x\|_{\infty} \leq \left|\det(L)\right|^{1/n}$. In particular, by the standard comparison between $l_2$  and $l_{\infty}$  norms, $ \|x\|_2 \leq \sqrt{n}\, \left|\det(L)\right|^{1/n}$. $$ Remarks:

 * The constant in the $L^2$  bound can be improved, for instance by taking the open ball of radius $ < l$  as $C$  in the above argument. The optimal constant is known as the Hermite constant.
 * The bound given by the theorem can be very loose, as can be seen by considering the lattice generated by $(1,0), (0,n)$ . But it cannot be further improved in the sense that there exists a global constant $$c$$ such that there exists an $$n$$-dimensional lattice $$L$$ satisfying $$\| x\|_2 \geq c {\sqrt{n}}\cdot \left|\det(L)\right|^{1/n}$$for all $$x \in L \setminus \{0\}$$. Furthermore, such lattice can be self-dual.
 * Even though Minkowski's theorem guarantees a short lattice vector within a certain magnitude bound, finding this vector is in general a hard computational problem. Finding the vector within a factor guaranteed by Minkowski's bound is referred to as Minkowski's Vector Problem (MVP), and it is known that approximation SVP reduces to it using transference properties of the dual lattice. The computational problem is also sometimes referred to as HermiteSVP.
 * The LLL-basis reduction algorithm can be seen as a weak but efficiently algorithmic version of Minkowski's bound on the shortest vector. This is because a $ \delta $ -LLL reduced basis $ b_1, \ldots, b_n $ for $ L $  has the property that $ \|b_1\| \leq \left(\frac{1}{ \delta - .25}\right)^{\frac{n-1}{4}} \det(L)^{1/n} $ ; see these lecture notes of Micciancio for more on this. As explained in, proofs of bounds on the Hermite constant contain some of the key ideas in the LLL-reduction algorithm.

Primes that are sums of two squares
The difficult implication in Fermat's theorem on sums of two squares can be proven using Minkowski's bound on the shortest vector.

Theorem: Every prime with $p \equiv 1 \mod 4$ can be written as a sum of two squares.

$$

Additionally, the lattice perspective gives a computationally efficient approach to Fermat's theorem on sums of squares: First, recall that finding any nonzero vector with norm less than $2p$ in $L$, the lattice of the proof, gives a decomposition of $p$  as a sum of two squares. Such vectors can be found efficiently, for instance using LLL-algorithm. In particular, if $b_1, b_2$ is a $ 3/4 $ -LLL reduced basis, then, by the property that $\|b_1\| \leq (\frac{1}{\delta - .25})^{\frac{n-1}{4}} \text{det}(B)^{1/n}$, $\|b_1\|^2 \leq \sqrt{2} p < 2p$. Thus, by running the LLL-lattice basis reduction algorithm with $ \delta = 3/4 $, we obtain a decomposition of $p$ as a sum of squares. Note that because every vector in $L$ has norm squared a multiple of $p$, the vector returned by the LLL-algorithm in this case is in fact a shortest vector.

Lagrange's four-square theorem
Minkowski's theorem is also useful to prove Lagrange's four-square theorem, which states that every natural number can be written as the sum of the squares of four natural numbers.

Dirichlet's theorem on simultaneous rational approximation
Minkowski's theorem can be used to prove Dirichlet's theorem on simultaneous rational approximation.

Algebraic number theory
Another application of Minkowski's theorem is the result that every class in the ideal class group of a number field $S$ contains an integral ideal of norm not exceeding a certain bound, depending on $K$, called Minkowski's bound: the finiteness of the class number of an algebraic number field follows immediately.

Complexity theory
The complexity of finding the point guaranteed by Minkowski's theorem, or the closely related Blichfeldt's theorem, have been studied from the perspective of TFNP search problems. In particular, it is known that a computational analogue of Blichfeldt's theorem, a corollary of the proof of Minkowski's theorem, is PPP-complete. It is also known that the computational analogue of Minkowski's theorem is in the class PPP, and it was conjectured to be PPP complete.

title: Minkowski's theorem


text:
Goddess worship

Goddess worship may refer to:
 * The worship of any goddess in polytheistic religions
 * Worship of a Great Goddess on a henotheistic or monotheistic or duotheistic basis
 * Hindu Shaktism
 * The neopagan Goddess movement
 * Wicca
 * Dianic Wicca

title: Goddess worship