A little use of number theory

For discussing Olympiad Level Number Theory problems
User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh
A little use of number theory

Unread post by SANZEED » Thu Jan 26, 2012 7:42 am

Suppose that you have $1995$ different integers written on a paper sheet, taken at a random.Can you put them along a circle so that for every two adjacent numbers,the ratio of the larger and smaller is a prime,not necessarily distinct,I think
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: A little use of number theory

Unread post by Phlembac Adib Hasan » Thu Jan 26, 2012 11:55 am

No.Actually it is not possible for odd numbers$\ge 1$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: A little use of number theory

Unread post by SANZEED » Tue Jan 31, 2012 11:29 pm

My solution:

Actually it's impossible for any 1995 integers.Suppose it's possible.Then let $a_{0},a_{1},....,a_{1995}$ be the integers in clockwise direction.Then $a_{k-1}/a_{k}$ is a prime or the reciprocal of a prime for $k=1,2,.....,1995$ with $a_{0}=a_{1995}$. Suppose, $m$ of these are reciprocals of primes.Since
\[\frac{a_0}{a_1}\cdot\frac{a_1}{a_2}\cdots\frac{a_{1994}}{a_{1995}}=1\]
This means the product of $m$ primes is equal to the product of $1995-m$ primes.Unique prime factorization shows that $1995-m=m$,which is impossible(why?) and brings the contradiction.
Last edited by Masum on Sat Oct 13, 2012 8:38 pm, edited 1 time in total.
Reason: Properly Latexed. It is safe to use the preview button. :)
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
nafistiham
Posts:829
Joined:Mon Oct 17, 2011 3:56 pm
Location:24.758613,90.400161
Contact:

Re: A little use of number theory

Unread post by nafistiham » Wed Feb 01, 2012 5:42 pm

Sanzeed edit it.
i would give a pm.but, this request is also to the moderators
\[\sum_{k=0}^{n-1}e^{\frac{2 \pi i k}{n}}=0\]
Using $L^AT_EX$ and following the rules of the forum are very easy but really important, too.Please co-operate.
Introduction:
Nafis Tiham
CSE Dept. SUST -HSC 14'
http://www.facebook.com/nafistiham
nafistiham@gmail

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: A little use of number theory

Unread post by Phlembac Adib Hasan » Wed Feb 01, 2012 7:33 pm

SANZEED wrote:My solution:

Actually it's impossible for any 1995 integers.Suppose it's possible.Then let $a_{0},a_{1},....,a_{1995}$ be the integers in clockwise direction.Then $a_{k-1}/a_{k}$ is a prime or the reciprocal of a prime for $k=1,2,.....,1995$ with $a_{0}=a_{1995}$.Suppose $m$ of these are reciprocals of primes.Since
$(a_{0}/a_{1})(a_{1}/a_{2}).....(a_{1994}/a_{1995})=1$
This means the product of $m$ primes is equal to the product of $1995-m$ primes.Unique prime factorization shows that $1995-m=m$,which is impossible(why?) and brings the contradiction.
My solve has only three lines.I've given first two in hint.It's your task to find the third.Again my solve works for every odd number$\ge 3$ to show that's impossible.
Hint :
Call the ratio a change.Notice that you can make only one change at each pair.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply