Phi Combo (Summer MAT 2021/7)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

innumerateguy

2178 posts

innumerateguy

#1 h Jul 24, 2021, 11:26 PM • 1 Y

Y by centslordm

The function $\phi(n)$ denotes the number of positive integers less than or equal to $n$ that are relatively prime to $n.$ Determine the number of positive integers $a,$ relatively prime to $77,$ such that there exists some integer $n$ satisfying
$\frac{\phi(n)}{n}=\frac{a}{77}.$ William Dai

This post has been edited 3 times. Last edited by innumerateguy, Jul 24, 2021, 11:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#2 h Jul 24, 2021, 11:29 PM • 2 Y

Y by centslordm, Aryan-23

i got 9?

probably wrong tho

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OlympusHero

17020 posts

OlympusHero

#3 h Jul 24, 2021, 11:37 PM • 1 Y

Y by centslordm

What's the answer to this one?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#4 h Jul 24, 2021, 11:38 PM • 1 Y

Y by centslordm

OlympusHero wrote:

What's the answer to this one?

no idea :/

tho i got 9

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Arrowhead575

2281 posts

Arrowhead575

#5 h Jul 24, 2021, 11:44 PM

Y by

I got the number of factors of 60? so 12

This post has been edited 1 time. Last edited by Arrowhead575, Jul 24, 2021, 11:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#6 h Jul 24, 2021, 11:45 PM

Y by

Arrowhead575 wrote:

I got the number of factors of 60? so 8

number of factors of 60 is 12 tho?

and your overcounting some btw

or maybe not...

This post has been edited 2 times. Last edited by pi271828, Jul 24, 2021, 11:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OlympusHero

17020 posts

OlympusHero

#7 h Jul 24, 2021, 11:46 PM

Y by

I guessed 16 oops now 1/9

Am crying

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Arrowhead575

2281 posts

Arrowhead575

#8 h Jul 24, 2021, 11:46 PM

Y by

sry, I meant 12. (I thought I got 8, but when i checked my answer i got 12)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#9 h Jul 24, 2021, 11:47 PM

Y by

OlympusHero wrote:

I guessed 16 oops now 1/9

Am crying

meh

this is probably aime problem 10-15 level and olympiad level, i wouldnt worry

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#10 h Jul 24, 2021, 11:48 PM

Y by

Arrowhead575 wrote:

sry, I meant 12. (I thought I got 8, but when i checked my answer i got 12)

the nine i got was 30,40,50,45,48,54,57,58,59

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

centslordm

4738 posts

centslordm

#12 h Jul 24, 2021, 11:49 PM • 1 Y

Y by Mogmog8

eleven

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bole

576 posts

Bole

#14 h Jul 24, 2021, 11:59 PM • 1 Y

Y by I-_-I

The answer is $8$ I believe

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3363 posts

pi271828

#15 h Jul 24, 2021, 11:59 PM

Y by

why is everyone getting different answers lol

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

innumerateguy

2178 posts

innumerateguy

#16 h Jul 25, 2021, 12:11 AM

Y by

The official answer is 8 from $2^3=8$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Pleaseletmewin

1574 posts

Pleaseletmewin

#17 h Jul 25, 2021, 12:13 AM • 1 Y

Y by mathtiger6

I didn't do MAT but this is pretty nice
Sol
#9

This post has been edited 2 times. Last edited by Pleaseletmewin, Jul 25, 2021, 12:17 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathtiger6

326 posts

mathtiger6

#18 h Jul 25, 2021, 12:14 AM • 1 Y

Y by TopNotchMath

$\frac{\phi(n)}{n} = \frac{a}{77}$ .
Clearly $77 \mid n$ .

$\frac{\phi(n)}{n} = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} \cdot \frac{6}{7} \cdot \frac{10}{11}$ , where the first three factors of the RHS could be multiplied or not into the expression. If there is a higher prime in the denominator, there would be no way to cancel it.

We then find
$\frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = \frac{a}{60},$ where the LHS's three factors could be multiplied in or not. Therefore, the answer is $2^3 = 8$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Arrowhead575

2281 posts

Arrowhead575

#19 h Jul 25, 2021, 12:27 AM

Y by

DOH, I had 8 and then changed to 12

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

samrocksnature

8791 posts

samrocksnature

#20 h Jul 25, 2021, 12:27 AM

Y by

I don't understand why $11,13,\ldots \not{\mid} n.$

This post has been edited 1 time. Last edited by samrocksnature, Jul 25, 2021, 12:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TopNotchMath

1747 posts

TopNotchMath

#21 h Jul 25, 2021, 12:51 AM • 1 Y

Y by samrocksnature

samrocksnature wrote:

I don't understand why $11,13,\ldots \not{\mid} n.$

When you simplify the LHS, you get the following.

You have $\left(1 - \dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\dots = \dfrac{a}{77}$
Clearly, we need to have $7,11 | n$ to get the denominator of $77$ . If we substitute this in, we get:

$60\left(1-\dfrac{1}{p_3}\right)\dots = a$
Primes greater than $5$ do not divide $60$ , and we used $7$ and $11$ to clear the denominator, so that is why.

This post has been edited 2 times. Last edited by TopNotchMath, Jul 25, 2021, 12:52 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7586 posts

asdf334

#22 h Jul 25, 2021, 1:01 AM • 1 Y

Y by centslordm

smh when you get the x1/2 x2/3 x4/5 thing then proceed to do 1 + 3 instead of 2^3

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Geometry285

902 posts

Geometry285

#23 h Jul 25, 2021, 1:25 AM

Y by

If $n=77k$ , we have $k=1$ makes $\phi(77)=10 \cdot 6 = 60$ . Now, for $k \ge 1$ , we have $\frac{60 \cdot \phi(k)}{77k} = \frac{a}{77}$ . Clearly, for $a$ to be a distinct positive integer, $\frac{\phi(k)}{k}$ must be a distinct value that divides $60$ , the only possible values of which $k = \{2,3,5 \}$ since $\frac{60}{k}$ is an integer, and $\phi(k)$ is positive. Now, associating any of these numbers results in a distinct output, so the total amount of sets for these $3$ numbers are $2^3=\boxed{008}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dchenmathcounts

2443 posts

dchenmathcounts

#24 h Jul 25, 2021, 2:02 AM

Y by

samrocksnature wrote:

I don't understand why $11,13,\ldots \not{\mid} n.$

11 actually must divide $n$ . Here's why no prime greater than $11$ can divide $n$ .

Consider the greatest prime that divides $n$ ; clearly $\phi(n)$ cannot be divisible by it, so it is in the denominator. However, the greatest prime divisor of $77$ is $11$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

samrocksnature

8791 posts

samrocksnature

#25 h Jul 25, 2021, 2:03 AM

Y by

dchenmathcounts wrote:

samrocksnature wrote:

I don't understand why $11,13,\ldots \not{\mid} n.$

11 actually must divide $n$ . Here's why no prime greater than $11$ can divide $n$ .

Consider the greatest prime that divides $n$ ; clearly $\phi(n)$ cannot be divisible by it, so it is in the denominator. However, the greatest prime divisor of $77$ is $11$ .

Wait oops mistype

Z K Y