$4.$ Let $N$ be an integer greater than $1$.Denote by $x$ the smallest positive integer with the following property:there exists a positive integer $y$ strictly less than $x-1$ , such that $x$ divides $N+y$.Prove that x is either $p^n$ or $2p$ , where $p$ is a prime number and $n$ is a positive integer
Problem
Source:
Tags: number theory
12.05.2018 16:39
Key: $x$ is the least positive integer that doesn't divide $N$ and $N-1$, and since two consecutive number cannot divide the same integer, it appears that for integers in $[2,x-1]$ either divided by $N$ or $N-1$ is alternant. The rest becomes trivial and I will not post it here.
12.05.2018 23:23
How can we prove $x$ is prime power or $2p$?
12.05.2018 23:46
Hi abbosjon2002 and liekkas for that observation you get only 1 point if you want , i will post the solution i had during the contest
22.05.2018 20:29
My solution Denote all integers with this property as good integers. Now for all other bad integers or integers which are not good $x$, $x|N+x-1$ or $x|N$ for any natural number $N>1$. Thus $$N\equiv 0,1\pmod{x}$$. Lets assume for the sake of contradiction that there are other solutions. Now lets assume $x$ to be the smallest good integer for a particular N. So $x=k\cdot p^l$ where p is a prime not dividing N. And $(k,p)=1$ Where $k\neq 1$ and if $k=2 $ then $l\neq 1$. Clearly $N\equiv 1\pmod{p^l}$-$(2)$ as $p^l$ must be a bad integer. If $$k\nmid N$$,$\implies k$ must be bad $\implies N\equiv 1\pmod{x}$ which is a contradiction. So we conclude that we must have some prime divisor of k dividing N-$(1)$ $\boxed{Case:1}$ $\bold{Claim}$ If k has atleast 2 other prime divisors than p,then $x$ is not the smallest good integer. $\bold{Proof}$ From $(1)$ We must have a prime divisor q that divides N. However choosing $q.p^l$ We get that $q.p^l$ is good As $N\equiv 0\pmod{q}$ contradicting the minimality of $x$.$\square$ $\boxed{Case:2}$ If $x=a^b.p^l$ where a is a prime and $b,l>1$ In this case $a|N$ from $(1)$, And hence we can easily get a smaller good integer which is a contradiction.$\square$ $\boxed{Case:3}$ Ultimately we are left with the case lf $x=qp$ where q and p are odd primes. Again from $(1)$ and $(2)$ we get $q|N$ However we can see that if $2|N$ we would get a smaller good integer $2p$ which would be a contradiction. So $N\equiv 1\pmod{2}$ However in this case too we get a smaller good integer $2q$ which is again a contradiction. $\square$. Hence we conclude that our initial assumption that x had other solutions except of the form $2p$ and $p^n$ was wrong.$\square$
31.03.2024 03:41
Can you explain better what do you call good and bad ?
01.04.2024 00:15
I hope it is correct. If a number does not satisfy the property stated in the problem, it is because this number divides either \( N \) or \( N - 1 \). Let's assume by contradiction that \( x \) is not a power of a prime and neither is the double of a prime; then \( x = p^a \cdot q^b \cdot K \), where \( p^a \mid N \) and \( q^b \mid N - 1 \) (indeed, if \( x \) were composed only of prime factors dividing only one of \( N \) or \( N-1 \), then \( x \) would also divide one of these two, which contradicts the thesis). Now let \( k \) be the smallest prime dividing \( N \) and \( h \) be the smallest prime dividing \( N - 1 \). Obviously \( hk \leq x \), so \( x = hk \) because \( hk \) does not divide \( N \) and \( N - 1 \). However, one of \( h \) and \( k \) is equal to 2 because one of \( N \) and \( N - 1 \) is even.