Let $p$ be an odd prime number. a) Show that $p$ divides $n2^n + 1$ for infinitely many positive integers n. b) Find all $n$ satisfy condition above when $p = 3$
Problem
Source: 2019 Saudi Arabia BMO TST I p1
Tags: number theory, divides, divisible, prime
23.12.2020 17:22
For part a ,if we observe 2^(p-1) ] is congruent to 1 mod p,since gcd(2,p)=1.Now we see if we let n=p-1,n*2^n is congruent to -1 mod p and hence our condition is satisfied but this is leading us somewhere ,Let n=(p-1).k,and search for any restriction on k.We see that n*2^n is congruent to -k mod p and hence our condition is satisfied when k is congruent to 1 mod p ,which occurs infinitely often. QED. As for part b,We replace p by three to get that the solutions of n are of the form 2k,where k is congruent to 1 modulo 3.
08.07.2022 19:53
a) Choose $n=(pk+1)(p-1)$ for every positive integer $k$. We are going to claim that $n$ satisfies $p\mid{n\cdot 2^n}+1$. By Fermat Little's Theorem, we have $$2^{p-1}\equiv {1} \pmod {p}.$$then $$2^n = 2^{(pk+1)(p-1)} \equiv 1 \pmod {p} .$$So that $$n.2^n +1\equiv (pk+1)(p-1)\cdot 1 +1 =p^2 k +p-pk \pmod {p}.$$Since there are infinitely number of form $(pk+1)(p-1)$ so we get the conclusion. b) We consider the cases $ n = 6k + i, \forall i = \overline{0,5} $ according to module 3 . Then the answer is $n = 6k + 1$ and $n = 6k + 2$ for all positive numbers $k$.