prime number in action

For discussing Olympiad Level Number Theory problems
the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

prime number in action

Unread post by the arrivals » Fri Jan 14, 2011 8:21 pm

prove that for every integer k the numbers 2k+1 and 9k+4 are relatively prime.
and find G.C.D of the two numbers (2k-1 and 9k+4) in terms of k or as a function of k. :cry:
the arrivals
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: prime number in action

Unread post by Moon » Mon Jan 17, 2011 1:15 pm

Part 1: $9(2k+1)-2(9k+4)=1$. So, if some $d$ divides both $2k+1$ and $9k+4$, then it divides $1$.
So the gcd is $1$.

Part 2: $2(9k+4)-9(2k-1)=17$. So the gcd is $1 \text{ or } 17$.
(It is easy to check that both we can attain both values as gcds)
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

Re: prime number in action

Unread post by the arrivals » Mon Jan 17, 2011 5:36 pm

how will you approach this
(a-b,a+b) greater or equal (a,b)
(a,b) means their gcd function
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

abir91
Posts: 52
Joined: Sun Dec 19, 2010 11:48 am

Re: prime number in action

Unread post by abir91 » Mon Jan 17, 2011 7:20 pm

$(a-b,a+b)=(a+b+a-b,a+b-a+b)=(2a,2b)=2(a,b) \geq (a,b)$
Abir

Have you read the Forum Rules and Guidelines?

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: prime number in action

Unread post by Moon » Mon Jan 17, 2011 8:16 pm

abir91 wrote:$(a-b,a+b)=(a+b+a-b,a+b-a+b)=(2a,2b)=2(a,b) \geq (a,b)$
Actually it is incorrect. For example, take $a=7,=4$. Then $(a,b)=(a-b,a+b)=1$
Solution:
Let $(a,b)=d$. Then $(a,b)=(da',db')=d(a',b')=d$
Now $(a-b,a+b)=d(a'-b',a'+b')$. We have $(a'+b)+(a'-b')=2a'$. So, $(a-b,a+b)=d \text { or } 2d \geq (a,b)$
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
leonardo shawon
Posts: 169
Joined: Sat Jan 01, 2011 4:59 pm
Location: Dhaka

Re: prime number in action

Unread post by leonardo shawon » Mon Jan 17, 2011 9:40 pm

amm, sorry, but whats GCD ?
and i didnt understand ur last two lines moon bhaia., and amm did u take a=7 and b=4 ??
Ibtehaz Shawon
BRAC University.

long way to go .....

User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Re: prime number in action

Unread post by Moon » Mon Jan 17, 2011 10:06 pm

GCD=Greatest Common Divisor (গসাগু in Bengali). For example the gcd of $2,4$ is $2$.
In the last two lines at first I showed that $(a-b,a+b)=d(a'-b-,a'+b')$. Then I examined the gcd of $(a'-b,a'+b')$.
The gcd must divide their sum=$2a'$. So it must divide $2$. So the gcd is either $2$ or $1$. (and therefore $(a+b,a-b)=2d, d$.)

BTW $7,4$ was a special example. Here we are taking about any $a,b$.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

abir91
Posts: 52
Joined: Sun Dec 19, 2010 11:48 am

Re: prime number in action

Unread post by abir91 » Tue Jan 18, 2011 10:25 am

আরে তাইতো, কি লেখছি! যাই হোক, তুমি না লিখা অন্যদের দিতে পারতা কোথায় ভুল হইছে। :)
Abir

Have you read the Forum Rules and Guidelines?

the arrivals
Posts: 41
Joined: Tue Dec 21, 2010 10:17 pm

Re: prime number in action

Unread post by the arrivals » Wed Jan 19, 2011 8:01 am

but picking up your example a=7,b=4 it does fulfil the require statement of the given condition of the question.whers the fault???
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: prime number in action

Unread post by Masum » Wed Jan 19, 2011 9:19 pm

the arrivals wrote:prove that for every integer k the numbers 2k+1 and 9k+4 are relatively prime.
and find G.C.D of the two numbers (2k-1 and 9k+4) in terms of k or as a function of k. :cry:
the arrivals
Let $g=gcd(2k-1,9k+4)$,then $g|2k-1|18k-9,18k+8$ so their difference too.So $g|17,g=1$ or $17$
First part is similar
One one thing is neutral in the universe, that is $0$.

Post Reply