How Do We Prove \(\forall n\in\mathbb{N}\;\varphi(n)\mid n\) Is False?

  • Thread starter Thread starter hadi amiri 4
  • Start date Start date
  • Tags Tags
    Phi Physics
Click For Summary
SUMMARY

The statement "\(\forall n\in\mathbb{N}\;\varphi(n)\mid n\)" is definitively false, as evidenced by the counterexample \(\varphi(3) \not\mid 3\). The discussion highlights that this statement only holds for specific integers such as 1, 2, 4, 6, 8, 12, and 16, as referenced in the OEIS sequence A007694. Participants clarify that deriving a contradiction is a valid method to demonstrate the falsehood of the statement, emphasizing the importance of arithmetic verification in proving such claims.

PREREQUISITES
  • Understanding of the Euler's totient function \(\varphi(n)\)
  • Familiarity with mathematical notation and logic
  • Knowledge of basic number theory concepts
  • Ability to interpret and analyze mathematical proofs
NEXT STEPS
  • Study the properties of the Euler's totient function \(\varphi(n)\)
  • Learn about the implications of counterexamples in mathematical proofs
  • Explore the OEIS sequence A007694 for further examples
  • Investigate methods for proving statements in number theory
USEFUL FOR

Mathematicians, students of number theory, and anyone interested in understanding the implications of the Euler's totient function and its applications in mathematical proofs.

hadi amiri 4
Messages
98
Reaction score
1
\foralln\inN\varphi(n)/mid/n
 
Physics news on Phys.org


i made a mistake in writing
 


I imagine you meant
\forall n\in\mathbb{N}\;\varphi(n)\mid n (which is false; \varphi(3)\!\not\,\,\mid3)
but I'm not sure what the question is.
 


how we prove
<br /> \forall n\in\mathbb{N}\;\varphi(n)\mid n<br />
 
Last edited by a moderator:


How we prove that?
\forall n\in\mathbb{N}\;\varphi(n)\mid n
 


how we prove the statement in post 3
 


\forall n\in\mathbb{N}\;\varphi(n)\mid n

hadi amiri 4 said:
how we prove the statement in post 3

You can't, it's false. It only holds for 1, 2, 4, 6, 8, 12, 16, ... = http://www.research.att.com/~njas/sequences/A007694 .
 
Last edited by a moderator:


Why can’t we derive a contradiction in order to show that it’s false?
 


roam said:
Why can’t we derive a contradiction in order to show that it’s false?

I gave a contradiction, 3, in my first post.
 
  • #10


CRGreathouse said:
I imagine you meant
\forall n\in\mathbb{N}\;\varphi(n)\mid n (which is false; \varphi(3)\!\not\,\,\mid3)
but I'm not sure what the question is.

hadi amiri 4 said:
how we prove the statement in post 3

CRGreathouse said:
\forall n\in\mathbb{N}\;\varphi(n)\mid n



You can't, it's false. It only holds for 1, 2, 4, 6, 8, 12, 16, ... = http://www.research.att.com/~njas/sequences/A007694 .

roam said:
Why can’t we derive a contradiction in order to show that it’s false?

CRGreathouse said:
I gave a contradiction, 3, in my first post.
CRGreathouse, he asked how you prove the contradiction you gave in post 3 and you answered "You can't, it's false. "! You were, of course, referring to his original post, not the post you quoted.

roam, you prove the contradiction by doing the arithmetic. What is \phi(3)?
 
Last edited by a moderator:
  • #11


HallsofIvy said:
CRGreathouse, he asked how you prove the contradiction you gave in post 3 and you answered "You can't, it's false. "! You were, of course, referring to his original post, not the post you quoted.

Ah. I took that to mean 'How do we prove the statement "\forall n\in\mathbb{N}\;\varphi(n)\mid n" from post #3', rather than 'How do we prove the statement "\forall n\in\mathbb{N}\;\varphi(n)\mid n [...] is false" from post #3'. To me, "\forall n\in\mathbb{N}\;\varphi(n)\mid n" was the only mathematical statement in post #3; "(which is false[...])" is a nonrestrictive clause. '"\forall n\in\mathbb{N}\;\varphi(n)\mid n" is false' would have been a mathematical statement, but one I only implied. That's why I was so confused by post #6.

Of course a contradiction is an easy way to show that \forall n\in\mathbb{N}\;\varphi(n)\mid n fails.
 

Similar threads

Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
1K
MHB Is $\phi(U)$ a Subspace of $\mathbb{R}^m$?
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Mean values of observables
  • · Replies 2 ·
Replies
2
Views
1K
High School Elegant way to prove ##AB^{n}## commute
  • · Replies 1 ·
Replies
1
Views
1K
Prove that ## \sum_{d\mid n}\sigma_{1}(d)\sigma_{1}(\frac{n}{d}) ##
  • · Replies 20 ·
Replies
20
Views
2K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
  • · Replies 1 ·
Replies
1
Views
1K
High School Popularizing a property for n-bonacci numbers without publishing it?
  • · Replies 12 ·
Replies
12
Views
2K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
  • · Replies 10 ·
Replies
10
Views
3K
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
  • · Replies 3 ·
Replies
3
Views
2K
MHB Why do we conclude that p|exactly one of b0,c0?
  • · Replies 3 ·
Replies
3
Views
2K