Talk:Euler's totient function
This is the talk page for discussing improvements to the Euler's totient function article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 12 months |
This level-5 vital article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
This page has archives. Sections older than 365 days may be automatically archived by Lowercase sigmabot III when more than 10 sections are present. |
Not Empty Set is that Correct - Puzzling
[edit]Empty set says (and not related in any way to the Greek letter Φ), but inspired by the letter Ø in the Norwegian and Danish alphabets.
My last month Mathematics Today Magazine from mtG has a sentence,-
"Empty set is subset of every set and every set is subset of itself. We denote by it by Φ or {}"
is that phi is small case, couldn't categorize on that font whether it is lower or upper alphabet.
And however, Φ(n) -> Phi(n) -> Euler's totient function
Maybe we can see through Article, and make reference of Empty set if it is relevance to do that as per the sentence made by mtG
—Dev Anand Sadasivamt@lk 02:26, 30 June 2018 (UTC)
Letter Phi in mathematics
[edit](From my talk page, + answer, Sapphorain (talk) 22:23, 26 December 2018 (UTC))
Hello, regarding your recent revert of my edit, could you provide me an example of some respectable mathematical writing where the author would use the glyphs "φ" and "ϕ" as different variables (to denote two different things)? --Alexey Muranov (talk) 22:08, 26 December 2018 (UTC)
- No I cannot, and I am not interested in finding one. But it is not the point. Two different ways of writing the same letter have been used in many instances to denote different objects. So the present precision is quite legitimate and there is no reason to suppress it. Sapphorain (talk) 22:23, 26 December 2018 (UTC)
- I agree with showing the two ways it is commonly written. Bubba73 You talkin' to me? 23:25, 26 December 2018 (UTC)
- Although they both refer to the Greek letter phi, the two are separate symbols. I believe they both should be shown or described. In fact, I have seen some fields of mathematics prefer one symbol to the other.—Anita5192 (talk) 23:28, 26 December 2018 (UTC)
Divisor Sum Proof Error
[edit]A line in the "Divisor Sum" portion under "Computing Euler's totient function" states "Any such k must clearly be a multiple of n/d, but it must also be coprime to d," but there are many fractions in the n = 20 example given where k is not coprime to d. For example, k = 2 and d = 10 are not coprime. I didn't know how to flag content for review, so I posted on the talk page. X9du (talk) 21:39, 3 May 2020 (UTC)X9du
Consistency of Notation
[edit]I think it is imperative that this article choose a consistent notation for phi. This has been mentioned before on the talk page (Different Phis and Letter Phi in Mathematics), however, it does not appear to be completely resolved. It is completely reasonable for a sentence in the intro to note, as it does now, that the totient "is written using the Greek letter phi as φ(n) or ϕ(n)". However, throughout the article, using different typeset versions of phi causes needless confusion for readers. I'd recommend the latex typeset capital phi (ϕ) since this appears to the be the standard in a wide variety of current works (e.g. [1], [2], [3] pg. 8). TripleShortOfACycle (talk - contribs) - (she/her/hers) 07:32, 7 April 2021 (UTC)
- The article has used φ for a long time. Please leave it like it is, changing notation is pointless and bound to produce heated and sterile arguments. There were 4 uses of ϕ instead of φ, I changed them for consistency, as φ is overwhelmingly more common in the article. Note that both are lowercase phi, the uppercase version is Ф instead. Tercer (talk) 08:30, 7 April 2021 (UTC)
- Thanks for making the change! I am more concerned with consistency than which version was ultimately chosen. TripleShortOfACycle (talk - contribs) - (she/her/hers) 11:53, 7 April 2021 (UTC)
@Sapphorain: Perhaps your browser is rendering the characters differently than mine? For me {{math|''φ''(''n'')}} gives me the loopy character φ(n), or in math mode , and {{math|''ϕ''(''n'')}} gives me the straight character ϕ(n), or in math mode . Do you get something different? In that case it's fine to change to math mode, so that all readers can see the difference, but then please also do it for {{math|''φ''(''n'')}}, otherwise it looks ugly. Tercer (talk) 10:52, 7 April 2021 (UTC)
- Yes, I will change to math mode: I don't get at all what you describe (I am on MacOS Big Sur)! Thank you! --Sapphorain (talk) 11:25, 7 April 2021 (UTC)
- The two variants of phi look correct in {{math}} mode on my browser: φ, ϕ. However, the first Unicode variant appears loopy on my edit window but is rendered as straight (with a shorter vertical bar) if not included into {{math}}: φ, ϕ. A further reason for avoiding raw html for mathematics. D.Lazard (talk) 11:37, 7 April 2021 (UTC)
- I'm on Firefox on Ubuntu, it renders φ, ϕ correctly in all cases. Doesn't matter, we need it to render correctly for all readers, and apparently only <math> does the job. Tercer (talk) 11:45, 7 April 2021 (UTC)
- The two variants of phi look correct in {{math}} mode on my browser: φ, ϕ. However, the first Unicode variant appears loopy on my edit window but is rendered as straight (with a shorter vertical bar) if not included into {{math}}: φ, ϕ. A further reason for avoiding raw html for mathematics. D.Lazard (talk) 11:37, 7 April 2021 (UTC)
Proof for the multiplicity of the totient function
[edit]I think it would be better is a full proof for the multiplicity of the totient function is furnished in this page. If someone disagrees, please say so. I will put up the proof 3 days after this message is posted if there is no opposition— Preceding unsigned comment added by NKRVVI (talk • contribs) 10:49, 16 September 2021 (UTC)
- What is the multiplicity of the totient function? D.Lazard (talk) 10:58, 16 September 2021 (UTC)
- If you mean multiplicative property of the totient function, the proof sketched in § Phi is a multiplicative function seems sufficient. D.Lazard (talk) 11:02, 16 September 2021 (UTC)
There is a proof outline. I think that with a little more explanation, it could become a full proof.NKRVVI (talk) 03:22, 17 September 2021 (UTC)
- We generally only include proof outlines, and not full proofs, for most articles. Proofs are typically included only when they are particularly enlightening, and not merely as a way to verify a mathematical truth. In most cases, an outline suffices for that. For verification, we can point to mathematical publications that contain the proofs. —David Eppstein (talk) 05:41, 17 September 2021 (UTC)
new reference
[edit]There is a new reference (currently #25) to StackExchange. StackExchange is not considered a reliable source. Bubba73 You talkin' to me? 07:46, 23 November 2021 (UTC)
- The other reference for the same claim, "Bordellès in the external links", refers to a long-removed deadlink, archived at https://web.archive.org/web/20120301060141/http://www.les-maths.net/phorum/read.php?5,359275,359275 but possibly not in the right version, which as an open forum also looks non-reliable. —David Eppstein (talk) 08:02, 23 November 2021 (UTC)
Number getting divided by their totient function
[edit]The only numbers which gets divided by (or is divisible by) their Euler's totient function are 1 which gives 1 as quotient, positive powers of 2 (2^k, k > 0) which gives 2 as quotient and a positive power of 2 multiplied by a positive power of 3 (2^a * 3^b, a > 0 and b > 0) which gives 3 as quotient. I have a proof of this: The values of totient function is always even except in cases of numbers 1 and 2 which have totient function value odd i.e., 1 (here). Why?
All numbers one less than a prime except 1 = 2 - 1 is even. All differences of consecutive powers of a given prime is also even. As two consecutive powers of the given prime are either both odd or both even (only in case of 2) and difference of two odd numbers or two even numbers is always even. All other numbers are combinations of these prime powers, so, it works out well for them too (as the only way to get odd product is to multiply two or more odd numbers and only 1 is the available odd value).
So, the only odd number (as odd numbers are not divisible by even numbers) which gets divided by its value of Euler's totient function is 1 (quotient = 1). Now, we are left with even numbers.
The difference between consecutive powers of a given prime = p^k - p^(k - 1) = (p - 1) * p^(k - 1). For a prime power to have such property, we have p^k/{(p - 1) * p^(k - 1)} = p/(p - 1). p - (p - 1) = 1. So, p - 1 should be a factor of 1. So, p - 1 = 1 => p = 2. So, only such prime powers are powers of 2 (as they are the only even prime powers).
As 2^k/{2^(k - 1)} = 2, they give quotient = 2 when they are divided by their Euler's Totient function value. As they must be even, they include a power of 2 in their prime factorization.
Number = 2^a * p^b
Totient function = 2^(a - 1) * (p - 1) * p^(b - 1)
Quotient = (2^a * p^b)/(2^(a - 1) * (p - 1) * p^(b - 1))
= 2 * p/(p - 1)
As from previous calculation, p = 2. But because of two on top and p and (p - 1) being always coprime. p - 1 should be a factor of 2. Either p - 1 = 1 or p - 1 = 2. So, p is either 2 or 3. As p should be coprime to 2, p is 3. So, numbers of form 2^a * 3^b with a > 0 and b > 0. Quotient = 2 * 3/(3 - 1) = 2 * 3/2 = 3.
Going to three prime factors:
Number = 2^a * p^b * q^c
Euler's Totient Function = 2^(a - 1) * (p - 1) * p^(b - 1) * (q - 1) * q^(c - 1).
Quotient = 2^a * p^b * q^c/(2^(a - 1) * (p - 1) * p^(b - 1) * (q - 1) * q^(c - 1)) = 2pq/((p - 1)(q - 1)).
As every prime p or q other than 2 are odd, so, p - 1 and q - 1 are both even. So, 2 is cancelled by p - 1 and because of q - 1, there is 2 in the denominator. As p and q are odd primes, the 2 will remain in the denominator. As the number of prime factors increases, the denominator will have more even numbers (especially powers of 2) in the denominator. As 1 is not even, no numbers with more than 2 prime factors have this property. 2409:40E0:1157:8BB6:E0A3:1E13:37CC:EAB7 (talk) 08:35, 8 October 2024 (UTC)
- In principle, this could be notable. But as it stands it is original research and would as such need a reliable source, ideally a peer-reviewed paper, in order to be included in its proper subsection. Lklundin (talk) 14:38, 9 October 2024 (UTC)
- See this video: this video. Bubba73 You talkin' to me? 02:44, 10 October 2024 (UTC)
- Definitely not a reliable source —David Eppstein (talk) 05:00, 10 October 2024 (UTC)
- Yes, I know, but it shows that the result is already known. Bubba73 You talkin' to me? 05:07, 10 October 2024 (UTC)
- Searching Google Scholar for "3-smooth" "totient" did not turn up any likely sources. —David Eppstein (talk) 05:53, 10 October 2024 (UTC)
- Yes, I know, but it shows that the result is already known. Bubba73 You talkin' to me? 05:07, 10 October 2024 (UTC)
- Definitely not a reliable source —David Eppstein (talk) 05:00, 10 October 2024 (UTC)
- See this video: this video. Bubba73 You talkin' to me? 02:44, 10 October 2024 (UTC)