Let $a>k$ be natural numbers and $r_1<r_2<\dots r_n,s_1<s_2<\dots <s_n$ be sequences of natural numbers such that: $(a^{r_1}+k)(a^{r_2}+k)\dots (a^{r_n}+k)=(a^{s_1}+k)(a^{s_2}+k)\dots (a^{s_n}+k)$ Prove that these sequences are equal.
Problem
Source: Iran second round 2018 day 1 problem 3
Tags: number theory
Taha1381
26.04.2018 12:11
Since $a>k$ there exists $p$ so that $v_p(a)>v_p(k)$ decrease the value of both sides by $k^n$ and take $v_p$ of sides we get: $v_p(k^{n-1}*a^{r_1})=v_p(k^{n-1}*a^{s_1}) \Rightarrow r_1=s_1$ now induct.
AlirezaOpmc
26.04.2018 12:17
Hey taha how was the exam? Just WLOG let $r_1<s_1$ then $s_i>r_1$ and then $s_i=q_i*r_1+p_i$ then you can simplify the $$a^{r_1}+k \mid (a^{s_1}+k)(a^{s_2}+k)\dots (a^{s_n}+k)$$to $$a^{r_1}+k \mid a^{p_1+p_2+...+p_n} * k^{q_1+q_2+...+q_n}$$now if $a\nmid k$ we have contradiction so $a\mid k$ then $a\le k$ and again contradiction with our first assumption.
Taha1381
26.04.2018 12:18
AlirezaOpmc wrote: Hey taha how was the exam? Terrible I missed problem 1
AlirezaOpmc
26.04.2018 12:29
Taha1381 wrote: Terrible I missed problem 1 awm I reached that $XY$ must be equal with $XC$ but I stopped here
ThE-dArK-lOrD
26.04.2018 12:33
Nothing, I was drunk.
alirezanorooz
26.04.2018 12:45
you can use G.C.D too!!
Taha1381
26.04.2018 13:00
Taha1381 wrote: I have a solution(I hope ):Since $a>k$ there exists a prime number $p$ so that $v_p(a)>v_p(k)$ decrease the value of both sides by $k^n$ and take $v_p$ of sides we get: $v_p(k^{n-1}*a^{r_1})=v_p(k^{n-1}*a^{s_1}) \Rightarrow r_1=s_1$ For the rest You can just induct. Is this correct?
AlirezaOpmc
26.04.2018 13:14
Too close to my first idea but I think it's correct but I am not sure taha
Hamel
26.04.2018 15:14
AlirezaOpmc wrote: Hey taha how was the exam? Just WLOG let $r_1<s_1$ then $s_i>r_1$ and then $s_i=q_i*r_1+p_i$ then you can simplify the $$a_{r_1}+k \mid (a^{s_1}+k)(a^{s_2}+k)\dots (a^{s_n}+k)$$to $$a_{r_1}+k \mid a^{p_1+p_2+...+p_n} * k^{q_1+q_2+...+q_n}$$now if $a\nmid k$ we have contradiction so $a\mid k$ then $a\le k$ and again contradiction with our first assumption. Where is the contradiction if $a \nmid k$?
Hamel
26.04.2018 15:15
....Ok.....
Taha1381
26.04.2018 15:57
Hamel wrote: Taha1381 wrote: I have a solution(I hope ):Since $a>k$ there exists a prime number $p$ so that $v_p(a)>v_p(k)$ decrease the value of both sides by $k^n$ and take $v_p$ of sides we get: $v_p(k^{n-1}*a^{r_1})=v_p(k^{n-1}*a^{s_1}) \Rightarrow r_1=s_1$ For the rest You can just induct. How do you skip all the others and reach to $v_p(k^{n-1}*a^{r_1})=v_p(k^{n-1}*a^{s_1}) \Rightarrow r_1=s_1$. It contradicts itself I think. If it is the only condition you had to check then why even use induction. It's simple the others have more prime powers in their factrorization.(Because $v_p(a)>v_p(k)$).And I used induction to just clearify my solution.
math-helli
26.04.2018 21:06
who is the author?
AlirezaOpmc
26.04.2018 21:11
AlirezaOpmc wrote: Hey taha how was the exam? Just WLOG let $r_1<s_1$ then $s_i>r_1$ and then $s_i=q_i*r_1+p_i$ then you can simplify the $$a_{r_1}+k \mid (a^{s_1}+k)(a^{s_2}+k)\dots (a^{s_n}+k)$$to $$a_{r_1}+k \mid a^{p_1+p_2+...+p_n} * k^{q_1+q_2+...+q_n}$$now if $a\nmid k$ we have contradiction so $a\mid k$ then $a\le k$ and again contradiction with our first assumption. More explaination: Let $a_{r_1} + k = M$ $a^{s_1}+k = a^{q_1 r_1+p_1} +k \equiv -ka^{(q_1-1) r_1+p_1} \equiv k^2 a^{(q_1-2) r_1+p_1} \equiv \cdots \equiv (-1)^n k^{q_1} a^{p_1}$ $a^{s_2}+k = a^{q_2 r_1+p_2} +k \equiv -ka^{(q_2-1) r_1+p_2} \equiv k^2 a^{(q_2-2) r_1+p_2} \equiv \cdots \equiv (-1)^n k^{q_2} a^{p_2}$ $\cdots$ $a^{s_n}+k = a^{q_n r_1+p_n} +k \equiv -ka^{(q_n-1) r_1+p_n} \equiv k^2 a^{(q_n-2) r_1+p_n} \equiv \cdots \equiv (-1)^n k^{q_n} a^{p_n}$ (mod M) $M \mid (-1)^{n^2} k^{q_1+q_2+\cdots + q_n} a^{p_1+p_2+/cdots + p_n}$
AlirezaOpmc
27.04.2018 19:20
My solution is wrong!
Abdollahpour
28.04.2018 11:28
Who can solve this problem by $gcd$ ?
rayuga
28.04.2018 14:28
We begin by defining $$M_{j}(r, n) =\sum_{1=i_{1} < i_{2} < ...< i_{j}=n} a^{\sum_{t=1}^{j} r_{i_{t}}}$$The statement obviously holds for $n=1$. So just
assume the statement holds for any $n-1$ such sequences. $WLOG$ assume that given sequence $r_{i}$ and $s_{i}$ for $i=1(1)n$ be those sequence which we will take to observe our induction hypothesis is true for $n$ or not.
Thus it is given for $n$ that $$(X=(\prod_{i=1}^{n} (a^{r_{i}}+k))-k^{n}) = ((\prod_{i=1}^{n} (a^{s_{i}}+k)) -k^{n}=Z) $$and name the above expression (*) which is equivalent to $$\sum_{i=1}^{n} k^{n-i}M_{i}(r, n)=\sum_{i=1}^{n} k^{n-i}M_{i}(s, n) $$. Name the above expression (#). Now let $r_{u} \neq s_{v}$(@) for $u, v$ in desired given limit and so $WLOG$ we can assume that $r_{1}=Min({r_{1},r_{2},...,r_{n},s_{1},s_{2},...s_{n}})$ Now we will consider $\pmod {a^{r_{1}+1}}$ to (#)
Which implies $$k^{n-1}a^{r_{1}} \equiv \sum_{i=1}^{n} k^{n-i}M_{i}(r, n) \equiv \sum_{i=1}^{n} k^{n-i}M_{i}(S, n) \equiv 0 \pmod{a^{r_{1}+1}}$$which implies $a$ divides $k^{n-1}$
Case 1: Let, $a|k$ then $k\geq a$ a contradiction to $a>k$. Thus there must exist a $s_{k}$ equaling $r_{1}$ in order to avoid the contradiction $WLOG$ we can pick $s_{k}=s_{1}$ hence we have $(a^{r_{1}}+1)=(a^{s_{1}}+1)$ hence by cancelling the equal factor from (*) after adding $k^{n}$ to both side of it we get $$(\prod_{i=2}^{n} (a^{r_{i}}+k)) = (\prod_{i=2}^{n} (a^{s_{i}}+k)) $$which by induction hypothesis equivalent to $(r_{2},r_{3},...,r_{n})=\sigma(s_{2},s_{3},...s_{n})$ and Thus $WLOG$ picking $r_{i}=s_{i}$ for every $i=2(1)n$ we have $$\boxed{(r_{1},r_{2},...,r_{n})=(s_{1},s_{2},...,s_{n})}$$.
Case 2: If $a|k^{m}$ where $m$ is the smallest integer that works to divisibility is $a$ and $k$ then we clearly see that $m>1$ thus there must exist a prime $p$ dividing $k$ such that $H=v_{p}(a) >v_{p}(k)=P$ then we see that
$$(H(\sum_{i=1}^{k_{1}} r_{i})+P(n-k_{1})))-(H(\sum_{i=1}^{k_{1}+1} r_{i})+P(n-k_{1}-1)))=-Hr_{k_{1}+1}+ P< 0$$Name the above expression (!) Now we see that $v_{p}(k^{n-k_{1}}M_{k_{1}}(e, n))=H(\sum_{i=1}^{k_{1}} e_{i})+P(n-k_{1})$ for $k_{1}=1(1)n-1$ Which implies by (!) that $v_{p}(k^{n-k_{1}}M_{k_{1}}(e, n))<v_{p}(k^{n-k_{1}-1}M_{k_{1}+1}(e, n))$ for $e=s,r$ and thus $$v_p(X)= v_{p}(k^{n-1}*a^{r_{1}})=v_{p}(k^{n-1}*a^{s_{1}})=v_{p}(Z) $$(by *) which implies $r_{1}=s_{1}$ which is a contradiction to (@) hence our assumption (@) is wrong thus minimal $r_{1}$ must be equaling some of the member in the sequence of $s_{i}$, so we can assume $WLOG$ we can assume $r_{1}=s_{1}$ which rises to
$$(\prod_{i=2}^{n} (a^{r_{i}}+k)) = (\prod_{i=2}^{n} (a^{s_{i}}+k)) $$which by induction hypothesis equivalent to $(r_{2},r_{3},...,r_{n})=\sigma(s_{2},s_{3},...s_{n})$ and Thus $WLOG$ picking $r_{i}=s_{i}$ for every $i=2(1)n$ we have $$\boxed{(r_{1},r_{2},...,r_{n})=(s_{1},s_{2},...,s_{n})}$$.
$\square$
Note : If $A$ is a tuple $\sigma({A})=B=$some permutation of the elements of tuple $A$.
(Case 2 is similar to the solution in 1st comment just with different direction) Edit: I tried to make my solution correct(It may be wrong again so please check) and Thanks @Taha1381 for finding the error in my previous solution
Taha1381
28.04.2018 14:38
rayuga wrote: Which implies $$k^{n-1}a^{r_{1}} \equiv \sum_{i=1}^{n} k^{n-i}M_{i}(r, n) \equiv \sum_{i=1}^{n} k^{n-i}M_{i}(S, n) \equiv 0 \pmod{a^{r_{1}+1}}$$which implies $a$ divides $k$ which means $k\geq a$ a contradiction to $a>k$. Q.E.D This implies $a|k^{n-1}$ not $a|k$.
Ahmadreza_kh
01.05.2018 17:17
because $a>k$ $\Rightarrow$ $\exists$ one p = prime number such that $v_{p}(a)>v_{p}(k)$ $a=p^\alpha a_1$ and $k=p^\beta k_1$ and $p \nmid$ $a_1,k_1$ $(a^{r_1}+k)(a^{r_2}+k)\dots (a^{r_n}+k)=(a^{s_1}+k)(a^{s_2}+k)\dots (a^{s_n}+k)$ if $r_1=s_1 \Rightarrow$ $(a^{r_2}+k)\dots (a^{r_n}+k)=(a^{s_2}+k)\dots (a^{s_n}+k)$ and with induction on count $r_i$ (Primary Mode is n) $\Rightarrow$ $r_i=s_i$ & $i\in {1,2,...,n} $ and n=1 is correct so bad mode is $r_1\neq s_1$ and because $r_i$ and $s_i$ are symmetric of each other so we can suppose that $r_1<s_1$ we are know$(a^{r_1}+k)(a^{r_2}+k)\dots (a^{r_n}+k)=(a^{s_1}+k)(a^{s_2}+k)\dots (a^{s_n}+k)$ $\to$ $(p^{\alpha r_1}a_1^{r_1}+p^\beta k_1)\dots(p^{\alpha r_n}a_1^{r_n}+p^\beta k_1)=(p^{\alpha s_1}a_1^{s_1}+p^\beta k_1)\dots(p^{\alpha s_n}a_1^{s_n}+p^\beta k_1)$ $\Rightarrow$ $(p^{\alpha r_1-\beta}a_1^{r_1}+ k_1)\dots(p^{\alpha r_n-\beta}a_1^{r_n}+ k_1)=(p^{\alpha s_1-\beta}a_1^{s_1}+ k_1)\dots(p^{\alpha s_n-\beta}a_1^{s_n}+ k_1)$ so $(p^{\alpha r_1-\beta}a_1^{r_1}+ k_1)\dots(p^{\alpha r_n-\beta}a_1^{r_n}+ k_1) \overset{p^{\alpha r_1-\beta+1}}{\equiv}(p^{\alpha s_1-\beta}a_1^{s_1}+ k_1)\dots(p^{\alpha s_n-\beta}a_1^{s_n}+ k_1)$ we know $\forall_{2\le i \le n}$ $r_1$<$r_i$ so $\alpha r_i-\beta\ge \alpha r_1-\beta +1$ so $p^{\alpha r_1-\beta+1} \mid p^{\alpha r_i-\beta}$ so $p^{\alpha r_i-\beta}+k_1 \overset{p^{\alpha r_1-\beta+1}}{\equiv} k_1$ and know $\forall_{1\le i \le n}$ $r_1$<$s_i$ $\alpha s_i-\beta\ge \alpha r_1-\beta +1$ so $p^{\alpha r_1-\beta+1} \mid p^{\alpha s_i-\beta}$ so $p^{\alpha s_i-\beta}+k_1 \overset{p^{\alpha r_1-\beta+1}}{\equiv} k_1$ so $(p^{\alpha r_1-\beta}a^{r_1}_1+k_1)k^{n-1}_ 1 \overset{p^{\alpha r_1-\beta+1}}{\equiv} k^{n}_1$ and because $p\nmid k_1$ and p is prime so gcd(p,k_1)=1 so $(p^{\alpha r_1-\beta}a^{r_1}_1+k_1)\overset {p^{\alpha r_1-\beta+1}}{\equiv} k_1$ so $p^{\alpha r_1-\beta+1} \mid p^{\alpha r_1-\beta}a^{r_1}$ so $p\mid a_1$ but $p\nmid a_1$
iman007
22.09.2020 20:19
Taha1381 wrote: Since $a>k$ there exists $p$ so that $v_p(a)>v_p(k)$ decrease the value of both sides by $k^n$ and take $v_p$ of sides we get: $v_p(k^{n-1}*a^{r_1})=v_p(k^{n-1}*a^{s_1}) \Rightarrow r_1=s_1$ now induct. what about the case $gcd(a,k)=1$ and no such $p$ exists!
AgentC
26.03.2024 17:58
iman007 wrote: what about the case $gcd(a,k)=1$ and no such $p$ exists! Hello, in that case every Prime p that $p|n$ has that property