13
$\begingroup$

I am dealing with the test of the OBM (Brasilian Math Olimpyad), University level, 2017, phase 2.

As I've said at another topic (question 1), I hope someone can help me to discuss this test.

The question 2 says:

Taking fixed positive integers $a$ and $b$, show that the set of the prime divisors of the sequence terms $a_n=a\cdot 2017^n+b\cdot 2016^n$ is infinite.

The only thing that is on my mind is Dirichlet's Theorem: Given any $k,k'\in\mathbb{Z}$ coprime, the arithmetic progression of reason k' and inicial term k has infinite primes.

However, I don't have ideas about how do it. Thanks very much.

Edit September, 01

I was searching about recurrences and I found a little about Lucas sequences, it seems important: Lucas sequence

$\endgroup$
15
  • 1
    $\begingroup$ what is $\gcd(a_n, a_m) \; ? $ It is not necessary for any of the terms $a_n$ to be prime, so Dirichlet is not involved. $\endgroup$
    – Will Jagy
    Commented Aug 27, 2018 at 21:50
  • 1
    $\begingroup$ @WillJagy: Hmm, rereading the problem, I think what I initially understood is probably a stronger statement than was actually asked for. $\endgroup$
    – hmakholm left over Monica
    Commented Aug 27, 2018 at 22:00
  • 1
    $\begingroup$ @Na'omi: Yes, that was what I ought to have said. Though, due to Fermat's little theorem, if $p\mid a_n$ for some $n\ge 1$, then we also have $p\mid a_{n+k(p-1)}$ for every $k\ge 0$, so the difference actually disappears (unless $p\mid a_0$, which is only the case for finitely many $p$). $\endgroup$
    – hmakholm left over Monica
    Commented Aug 27, 2018 at 22:17
  • 1
    $\begingroup$ @HenningMakholm it might be something like the Fibonacci numbers, $F_m$ and $F_n$ are coprime if $m,n$ are coprime. proofwiki.org/wiki/GCD_of_Fibonacci_Numbers This is more realistic than the Fermat number example, as we are looking at a degree two linear recurrence here. $\endgroup$
    – Will Jagy
    Commented Aug 27, 2018 at 23:06
  • 1
    $\begingroup$ @WillJagy: Not at all. The observation that the $a_n$s satisfy a second-order recurrence is interesting. $\endgroup$
    – hmakholm left over Monica
    Commented Aug 27, 2018 at 23:37

1 Answer 1

Reset to default
6
$\begingroup$

Suppose the set of primes dividing the sequence is finite instead, and number them $p_1,...,p_K.$

Associate to each term $a_n = a \cdot 2016^n + b \cdot 2017^n$ the index $i, 1 \le i \le K,$ such that biggest prime power that divides $a_n$ is $p_i^{\beta_i(n)}$.

By the pigeonhole principle, there is an index $i_0$ and $a_n,a_m,\,m>n,m-n \le K,$ such that $a_n,a_m$ are both associated to $i_0,$ for each $n.$ Therefore, letting $l = \min(\beta_{i_0}(n),\beta_{i_0}(m)),$ we get that

$$ p_{i_0}^l | a\cdot 2016^n + b\cdot 2017^n, p_{i_0}^l | a \cdot 2016^m + b\cdot 2017^m.$$

The relations above imply, on the other hand, that

$$ p_{i_0}^l | b\cdot(2016^{m-n} - 2017^{m-n}). $$

From the fact that the number of primes is bounded, we get that $p_{i_0}^{l \cdot K} \ge 2017^n.$ On the other hand, by the equation above,

$$ p_{i_0}^l \le C \cdot 2017^K.$$

As $K$ is fixed, we see that

$$ 2017^{\frac{n}{K} - K} \le C, \text{for infinitely many } n \in \mathbb{N}.$$

This leads to a contradiction by letting $n \to \infty.$

$\endgroup$
5
  • 1
    $\begingroup$ Thanks very much for the great help, but I'm still trying understand how you could get $p_{i_0}^l | b\cdot(2016^{m-n} - 2017^{m-n})$, could you explain, please? Thanks again. $\endgroup$
    – Quiet_waters
    Commented Sep 13, 2018 at 14:09
  • 2
    $\begingroup$ @Na'omi Of course! :D So, from the equations we have that $p_{i_0}^l | 2016^{m-n}(a \cdot 2016^n + b \cdot 2017^n) = a \cdot 2016^m + b \cdot 2016^{m-n} \cdot 2017^n.$ Subtracting the other relation, it yields $p_{i_0}^l | b \cdot 2016^{m-n} \cdot 2017^n - b \cdot 2017^m = 2017^n \cdot b \cdot (2016^{m-n} - 2017^{m-n}).$ By a similar method, we get also that $p_{i_0}^l | 2016^n \cdot a\cdot(2017^{m-n} - 2016^{m-n}).$ Finally, as $\text{gcd}(2016,2017) = 1,$ we get that either $p_{i_0}^l | a\cdot(2017^{m-n} - 2016^{m-n})$ or $p_{i_0}^l | b\cdot(2017^{m-n} - 2016^{m-n}).$ $\endgroup$
    – João Ramos
    Commented Sep 13, 2018 at 14:48
  • $\begingroup$ @Na'omi we just assume that in the above the second option happens to simplify things! $\endgroup$
    – João Ramos
    Commented Sep 13, 2018 at 14:49
  • $\begingroup$ NOW I think I could understand, I thank you very much! This question was very difficult to me. $\endgroup$
    – Quiet_waters
    Commented Sep 14, 2018 at 22:54
  • 1
    $\begingroup$ How do you know this $p_{i_0}^{l \cdot K} \ge 2017^n.$? $\endgroup$
    – João Víctor Melo
    Commented Jan 9, 2022 at 15:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .