gcd and divisibility

For discussing Olympiad Level Number Theory problems
kh ibrahim
Posts: 17
Joined: Mon May 09, 2016 11:18 am

gcd and divisibility

Unread post by kh ibrahim » Sat Aug 20, 2016 2:47 pm

If a multiple of 864 is taken which is a positive integer,then what is the probability of that number to be divisible by 1944

User avatar
nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

Re: gcd and divisibility

Unread post by nahin munkar » Sun Aug 21, 2016 12:55 am

The ans is $ \dfrac{1}{ 9} $.
It's a very easy problem. Here,By PPF, $ 864 $ = $ 2^5 * 3^3 $ . & $ 1944 = 2^3 * 3^5 $ . Here, $ \frac{ 864}{ 1944 } $=$ \frac{2^2}{3^2} $ =$ \frac{4}{9} $. The probability of a multiple of $ 4 $ is divisibled by $ 9 $ is $ \frac{ 1}{9 } $ ,as $ 4 $ & $ 9 $ are relatively prime..... :D
Last edited by nahin munkar on Mon Aug 22, 2016 1:57 pm, edited 1 time in total.
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

kh ibrahim
Posts: 17
Joined: Mon May 09, 2016 11:18 am

Re: gcd and divisibility

Unread post by kh ibrahim » Sun Aug 21, 2016 2:29 am

can u describe the probability part a bit more clearly?

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: gcd and divisibility

Unread post by asif e elahi » Sun Aug 21, 2016 1:09 pm

Take $864k$ as a multiple of $864$. Now if $1944$ divides $864k$, we must have $\dfrac{864k}{1944}\in \mathbb{N}$. Which implies $9\mid k$. The probability of happening this is $\dfrac{1}{9}$ when we choose $k$ randomly.

kh ibrahim
Posts: 17
Joined: Mon May 09, 2016 11:18 am

Re: gcd and divisibility

Unread post by kh ibrahim » Sun Aug 21, 2016 7:44 pm

I got that divisibility part that 9 is the factor of k but I I didn't get the probability part.if u could interpret how to determine the probability It would be percieved...thanx

User avatar
nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

Re: gcd and divisibility

Unread post by nahin munkar » Sun Aug 21, 2016 8:14 pm

kh ibrahim wrote:I got that divisibility part that 9 is the factor of k but I I didn't get the probability part.if u could interpret how to determine the probability It would be percieved...thanx
OK . If $ 9|k$, then $k$ is divided by $9$ only when it is a multiple of $9$. Then u will get $ k$ as a multiple of $9$ after each $9$ numbers . Observe $9,18,27,36..$...etc are multiple of $9$ .Look they r returning back as each $9th$ number ($8$ number after after). If u make use of probability formula then u get that $ k$ returns as a multiple of $9$ after each $9$ numbers. So, u'll get 1 number from any consequent $9$ numbers. Mainly, the probability version tells us u will get 1 number k as multiple of $9$ if u choose $9$ numbers.So, the probability is $ \dfrac{1}{9}$ as follows.
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

Post Reply