Find all numbers with given value of $\phi(n)$

Error

There was an error loading the page.

Contributors

Newcastle University Mathematics and Statistics

History

○

Newcastle University Mathematics and Statistics 9 years, 2 months ago

Created this.

There is only one version of this question that you have access to.

Question statement

Give any introductory information the student needs.

			Name	Type	Generated Value

pairs	list	Nested 19×2 list
p	list	List of 14 items
chkmp	list	List of 14 items
j	integer	0
tp	integer	6
bp1	number	7
gcp	number	2
bfp	integer	7
bp	integer	14
tp1	number	3
ordp	list	[ 2, 7 ]

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
[[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[1,3],[1,5],[1,7],[1,10],[2,4],[2,10],[2,12],[3,9],[3,13],[4,8]]

JME function reference

Description

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `list`

[ [ 0, 3 ], [ 0, 4 ], [ 0, 5 ], [ 0, 6 ], [ 0, 7 ], [ 0, 8 ], [ 0, 9 ], [ 0, 10 ], [ 0, 11 ], [ 1, 3 ], [ 1, 5 ], [ 1, 7 ], [ 1, 10 ], [ 2, 4 ], [ 2, 10 ], [ 2, 12 ], [ 3, 9 ], [ 3, 13 ], [ 4, 8 ] ]

→ Used by:

chkmp
ordp

This variable doesn't seem to be used anywhere.

Parts

Gap-fill
1. Gap Choose several from a list
  Add
1. Step Information only

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

Find all natural numbers $n$ such that $\phi(n)=\simplify[std]{{tp1}/{bp1}}n$

You are given that the general form of $n$ is

$n = p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_s^{\alpha_s}$

for a fixed set of primes $p_1,\;p_2,\ldots,p_s$ where $\alpha_j \ge 1\;\;j=1,\ldots,\;s$ .

Select the primes involved from these choices.

Unnamed gap

Note that you are deducted one mark for every wrong choice. The minimum mark is 0.

Advice

We can write the formula for the Euler Totient Function for

$n = p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_s^{\alpha_s},\;\;\;\alpha_j \ge 1\;\;j=1,\ldots,\;s$ as

$\phi(n)= n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)$
Hence we have:

$\begin{eqnarray*} \phi(n)= n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)&=&\simplify[std]{{tp1}/{bp1}}n \Rightarrow\\ \left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)&=&\simplify[std]{{tp1}/{bp1}} \end{eqnarray*}$

It is clear from the denominator of $\frac{\var{tp1}}{\var{bp1}}$ that the prime $\var{ordp[1]}$ must be in the factorization of $n$ .
We can assume that $p_1=\var{ordp[1]}$ .
Substituting these values in the identity above gives:

$\begin{eqnarray*} \left(1-\frac{1}{\var{ordp[1]}}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)&=&\simplify[std]{{tp1}/{bp1}}\Rightarrow\\ \left(\frac{\var{ordp[1]-1}}{\var{ordp[1]}}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)&=&\simplify[std]{{tp1}/{bp1}}\Rightarrow\\ \left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_s}\right)&=&\frac{\var{ordp[0]-1}}{\var{ordp[0]}} \end{eqnarray*}$
Hence we see that

$\var{ordp[0]}$ is also in the prime decomposition of

$n$ and putting

$p_2=\var{ordp[0]}$ we find:

$\begin{eqnarray*} \left(\simplify[std]{{ordp[0]-1}/{ordp[0]}}\right)\left(1-\frac{1}{p_3}\right)\cdots \left(1-\frac{1}{p_s}\right)&=&\frac{\var{ordp[0]-1}}{\var{ordp[0]}}\\ \end{eqnarray*}$

But the only way that can happen is when there are only the two primes we have already found.

Hence we see that $\var{ordp[0]}$ and $\var{ordp[1]}$ are the only two primes in the factorization of $n$ and that:

$n =\var{ordp[0]}^{\alpha_1}\var{ordp[1]}^{\alpha_2},\;\;\alpha_1,\;\;\alpha_2 \ge 1$

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Gap-fill
Gap-fill		Hasn't run yet
Choose several from a list
Choose several from a list		Hasn't run yet
Information only

This question is used in the following exams:

Loading...

Error

Find all numbers with given value of $\phi(n)$

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Newcastle University Mathematics and Statistics 9 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: `list`

Parts

Gap-fill

Loading...

Error

Find all numbers with given value of ϕ(n)\phi(n)

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Newcastle University Mathematics and Statistics 9 years, 2 months ago

Error in variable testing condition

Error

Warning

Generated value: list

Parts

Gap-fill

Find all numbers with given value of $\phi(n)$

Generated value: `list`