# First CS's inequality

Prove/Disprove the following inequality.

$\sum_{cyc}\sum_{k=1}^{M}\phi(a_1^k)\geq\sum_{cyc}\sum_{k=1}^{M} \phi (a_1)^k$

For all $$0\leq a_1 , a_2 , a_3 , ....., a_n \leq M$$ and $$M$$ is any natural number.

I have made the inequality more generalized.

Notation: $$\phi(\cdot)$$ denotes the Euler's totient function.

You may also see Second CS's inequality

Note by Chinmay Sangawadekar
2 years, 4 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

## Comments

Sort by:

Top Newest

Not quite sure about this, correct me if I make a mistake somewhere.

Let $$p$$ denotes an arbitrary prime number and let $$k,b \geq 1 \in \mathbb{N}$$

$$p^{k-1} \geq (p-1)^{k-1}$$

$$p^{-1} \geq p^{-k}(p-1)^{k-1}$$

$$p^{kb-1}(p-1) \geq p^{kb-k}(p-1)^{k}$$

$$p^{kb}-p^{kb-1} \geq {(p^{b}-p^{b-1})}^{k}$$

$$\phi(p^{kb}) \geq {\phi(p^{b})}^{k}$$, noting that $$\phi(p^{n})=p^{n}-p^{n-1}$$

Let $$a={p_{1}}^{k_{1}}{p_{2}}^{k_{2}}\cdots{p_{n}}^{k_{n}}$$.

From the result above, we have

$$\phi({p_{1}}^{kb_{1}})\phi({p_{2}}^{kb_{2}})\cdots\phi({p_{n}}^{kb_{n}}) \geq \phi{({p_{1}}^{b_{1}})}^{k}\phi{({p_{2}}^{b_{2}})}^{k}\cdots\phi{({p_{n}}^{b_{n}})}^{k}$$

$$\phi(a^{k}) \geq {\phi(a)}^{k}$$

Therefore, the inequality holds true, with equality holds only when $$a,b,c \in \{0,1\}$$ or $$M=1$$.

- 2 years, 4 months ago

Log in to reply

Comment deleted Mar 04, 2016

Log in to reply

Done.

- 2 years, 4 months ago

Log in to reply

Nicely done ! I don't think that there will be any mistake...@ZK LIn

- 2 years, 4 months ago

Log in to reply

Thanks! Glad to know that.

- 2 years, 4 months ago

Log in to reply

Can't it be true for arbitary numbers ?

- 2 years, 4 months ago

Log in to reply

The inequality holds true for all numbers. What I meant was conditions for equality cases.

- 2 years, 4 months ago

Log in to reply

Oh , initially I proved this inequality for arbitary primes , Can this inequality have significance in problem solving or in any theorem proofs ?

- 2 years, 4 months ago

Log in to reply

Number theoretic inequalities are quite rare in math olympiads, so I guess it won't be that helpful? However, this is a nice result. I can imagine it being useful in theorem proofs, but I have not encountered enough number theory literature to see an application of this result yet.

- 2 years, 4 months ago

Log in to reply

@Otto Bretscher What is your opinion ?

- 2 years, 4 months ago

Log in to reply

Didn't we do this inequality in the first batch already, question 2?

It is good to know the equation $$\phi(n^k)=n^{k-1}\phi(n)$$; this inequality is an immediate consequence.

- 2 years, 4 months ago

Log in to reply

Comment deleted Mar 04, 2016

Log in to reply

As you know, there is a big difference between Olympiad problems and "real mathematics". In hundreds of seminar talks I have attended at many universities, where people present their research papers, I have never heard anybody talk about number theoretical inequalities (or inequalities in general).

- 2 years, 4 months ago

Log in to reply

Do you think that such inequalities will be useful for ay theorem proofs or problems ? @Otto Bretscher

- 2 years, 4 months ago

Log in to reply

Comment deleted Mar 04, 2016

Log in to reply

Sure, why not?

- 2 years, 4 months ago

Log in to reply

For $$k>1$$,

$\phi(a^k)=a^{k-1}\phi(a)$

Since

$\phi(a)<a$

$\phi(a)^k<a^{k-1} \phi(a)=\phi(a^k)$

For k=1, the result $$\phi(a^k)=\phi(a)$$ is trivial.

The result above follows.

- 2 years, 4 months ago

Log in to reply

Exactly ! :)

- 2 years, 4 months ago

Log in to reply

Comment deleted Mar 02, 2016

Log in to reply

Bro, I see that you have studied all these awesome stuffs!

Can you please suggest me resources for studying them?Thanks!

(I mean modular arithmetic)

- 2 years, 4 months ago

Log in to reply

You can see that the inequality is proved , I had proved this only for arbitary peimes , and I am searching a more general proof , as you xan see the generalized inequality ... I will be glad to hear your opinions related to this new NT inequality.. @Harsh Shrivastava

- 2 years, 4 months ago

Log in to reply

I will try this in a few days,sorry a bit busy with board stuffs.

- 2 years, 4 months ago

Log in to reply

Comment deleted Apr 30, 2017

Log in to reply

I am not good in inequalities.

People like @ZK LIn @MS HT @gurido cuong are real inequality gods.

Please suggest us how to become good at inequalities ?

Thnx!

- 2 years, 4 months ago

Log in to reply

You are too generous with your compliment. I am definitely nowhere near the levels of @MS HT and @Gurido Cuong. They post new inequality problems at a rate faster than I can solve them, and I am nowhere near the level of a 'god' either.

However, since you ask for advice, I will do my best to provide them.The "advice" below comes from my personal experience and might not work for everyone, so take it with a pinch of salt.

I initially start studying inequalities seriously from the excellent note Mildorf "Olympiad Inequalities", which I believe is available somewhere on the web (AoPS maybe?). You might find that helpful.

A more elementary version of this is Siamin Riasat "Basics in Olympiad Inequalities". When I am a complete newbie, I rely on it heavily and tried (unsuccessfully) to solve all the problems. Easy as the questions are, they provide a good chance for you to apply the inequalities introduced.

- 2 years, 4 months ago

Log in to reply

I'm not good as you think.Because I'm not better than many people in my school or my social...

- 2 years, 4 months ago

Log in to reply

- 2 years, 4 months ago

Log in to reply

I can't help but notice that i am a member of that site.

BTW your joke was awesome.I am rolling over floor laughing.I appreciate efforts that you put in making this joke.You must consider a career as a stand-up comedian.Hats off to you!

- 2 years, 4 months ago

Log in to reply

I like your sense of sarcasm :3 Preserve it, not many have that.

- 2 years, 4 months ago

Log in to reply

LOL! :3 :3 :3

- 2 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...