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
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.
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.
26.04.2018 12:18
AlirezaOpmc wrote: Hey taha how was the exam? Terrible I missed problem 1
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
26.04.2018 12:33
Nothing, I was drunk.
26.04.2018 12:45
you can use G.C.D too!!
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?
26.04.2018 13:14
Too close to my first idea but I think it's correct but I am not sure taha
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$?
26.04.2018 15:15
....Ok.....
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.
26.04.2018 21:06
who is the author?
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}$
27.04.2018 19:20
My solution is wrong!
28.04.2018 11:28
Who can solve this problem by $gcd$ ?
28.04.2018 14:28
(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
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$.
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$
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!
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