## 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

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.
the arrivals
women of purity are for men of purity and hence men of purity are for women of purity - THE HOLY QURAN

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

### Re: prime number in action

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

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

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

$(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?

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

### Re: prime number in action

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

learn how to write equations, and don't forget to read Forum Guide and Rules.

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

### Re: prime number in action

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 .....

Moon
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Contact:

### Re: prime number in action

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

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

আরে তাইতো, কি লেখছি! যাই হোক, তুমি না লিখা অন্যদের দিতে পারতা কোথায় ভুল হইছে।
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

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

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
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$
One one thing is neutral in the universe, that is $0$.