Problem Set 3

[*Mahi*]

Thanks!

Nice solution Mahi, but how do you figure it out?

You know, just playing with $x^3,(x+1)^3,(x-1)^3$ and then

[Phlembac Adib Hasan]

Actually you should say that, let $p^a|m$ for a prime $p$ such that $p^{a+1}$ does not divide $m$. If we can prove that $p^a|n!$ then we are done since distinct primes are always co-prime.

Actually I didn't thought in this way.As every composite number can be written as multiplication of prime powers, if we prove it for prime powers, it will be proved for all $m$s.It's the same sense, but if we think in this way then my statement needs no correction.Now proof of number 8:

Lemma: If $q^m \equiv 1 (mod \; w)$ & $q^n \equiv 1 (mod \; w)$ and $(m,n)=g$ then $q^g \equiv 1(mod \; w) $
Its proof is very easy.Hint: Vieta Jumping.
The given condition states,\[2^{2a}\equiv 1(mod\; b)\]
\[2^{2b}\equiv 1(mod\; c)\]
\[2^{2c}\equiv 1(mod\; a)\]
Now we'll show that $2^ {2b}, 2^{2c},2^{2a}$ is the lowest power of $2$ that congruent to $1$ mod $c,a,b$ ,respectively if any of $a,b,c>3$.
Let $2^x$ is the lowest power of $2$ that congruent to $1\; (mod\; b)$ and $x<2a$.If $(x,2a)=g$,then from our lemma we can say that $2^g \equiv 1(mod\; b)$.If $g<x$, then $x$ is not such lowest power.And a contradiction.It implies that $x|2a$.As $2$ and $a$ are co-primes, $x|2$ or $x|a$ or $x=2p$ where $p|a$.If we find such $p$s for all of $a,b,c$ then the proof is similar to the proof of $2^ {2b}, 2^{2c},2^{2a}$ is the lowest power of $2$ that congruent to $1$ mod $c,a,b$ .As $2^a \equiv -1 (mod\; b)$, If $x |a$, it's impossible to exist such $x$.If $x|2$,then $x=1,2$.It implies $b=1,3$ Similar method to $a,c$ also gives $a,c=1,3$ Thus we find $(a,b,c)=(1,1,1)$.So it is not possible to exist such $x$s for all of $a,b,c$.It's very easy to prove if one or two from $a,b,c$ has such $x$s and the others do not- this case is possible only for $(a,b,c)=(1,3,1)$ or any cyclic permutation of it.And for other cases $2^ {2b}, 2^{2c},2^{2a}$ is the lowest power of $2$ that congruent to $1$ mod $c,a,b$ ,respectively.
But as $a,b,c$ are mutually co-primes, $2^ { \phi (b) }\equiv 1 (mod\; b)$...and cyclicly for others.
So $ 2a \leq \phi (b) < b$
$\Rightarrow b>a$
Similarly, $c>b$ and $a>c$.A contradiction.So solutions are $ (a,b,c)=(1,1,1),(1,1,3),(1,3,1),(3,1,1)$

[Masum]

Alas! The problem itself finds the solution for you!! That is a legendary idea.

[sourav das]

Now it's enough to show that $\sum_{k\geq 1} \left \lfloor \frac{n}{p^k} \right \rfloor \ge p^a$

Actually, $\sum_{k\geq 1} \left \lfloor \frac{n}{p^k} \right \rfloor = $ The highest power that divide $n!$. So if thought $P^a||m$ and $P^a||n!$ then you have proved that $a \geq P^a$. Actually it doesn't make any sense to me. May be i couldn't get your solution correctly or you just make a bug. Please explain your solution to us more briefly.

[sourav das]

As $2$ and $a$ are co-primes, $x|2$ or $x|a$

What if $x=2k$ where $(2,k)=1$ , $2|2$, $k|a$. Are you considering $x$ a prime?I didn't get your solution...

[sourav das]

Thanks!

Nice solution Mahi, but how do you figure it out?

You know, just playing with $x^3,(x+1)^3,(x-1)^3$ and then

SUPER COOL. Do you have any source or pdf or problems using this kind of tricks. Can you share with us? Same question for all (Specially to Masum bhai)

[Masum]

Thanks!

Nice solution Mahi, but how do you figure it out?

You know, just playing with $x^3,(x+1)^3,(x-1)^3$ and then

SUPER COOL. Do you have any source or pdf or problems using this kind of tricks. Can you share with us? Same question for all (Specially to Masum bhai)

In representation type problems, I generally at first try with the parameters with conjugate numbers like $a+b,a-b$ or something like that, and it is obvious since we can cancel many terms after the expansion. Those are useful in many problems.
For this problem particularly, consider with $x+1,x-1$ or $1+x,1-x$. Also notice that "not necessary distinct", so you should think about $x^3+(-x)^3$. But still you need to take care of something further.

[Nadim Ul Abrar]

No 8:

$2^{2a}\equiv1(modb)$
$2^{2b}\equiv1(modc)$
$2^{2c}\equiv1(moda)$

a,b,c wont be even . So that
If b \geq 3
$2^{(2a,\phi(b))} \equiv 2^2 mod \equiv 1(modb)$ (i)
else $b=1$ (ii)
let $a=2n+1$ then for (i)
$2^{2n+1}+1=2^a+1 \equiv 3 \equiv 0( mod b)$
or $b=3$

Thus we can say $c=1,3$,$a=1,3$ are possible values of $b,c$ too.

$ a,b,c$ be pairwisely co prime ,
So that all possible triple is $(1,1,1)$ and permutations of$(3,1,1)$

[Masum]

$2^{2a}\equiv1(modb)$
$2^{2b}\equiv1(modc)$
$2^{2c}\equiv1(moda)$

let $a \geq b \geq c$

then $\phi(b)|2a$,
$\phi(c)|2b$ .

Ha ha, those common mistakes I was talking about in another post. How can you say $\varphi(b)|2a$ without proof? At most what you can say is $2^{\gcd(2a,\varphi(b))}\equiv1\pmod b$, and the condition is still remains true. Got it? Your claim is not true always. But $a,b,c$ are only odd positive integers, not primes or something like that. And you may try with order, or something else. And in another post I saw right the mistake I was talking about with Shourov in another post. $x|2k$ with $k$ odd and someone concluded $x|2$ or $x|k$.
As I say, making silly but highly important flaws in number theory is very easy, may be easier than understanding the problem.

[Nadim Ul Abrar]

@ masum vaia : is it OK now ?