Intereting Posts

Use Euclid's Algorithm to find the multiplicative inverse
How would one be able to prove mathematically that $1+1 = 2$?
Hilbert vs. De Morgan
Find the total number of zeros in given range of decimal numbers
Modular arithmetic for negative numbers
Fibonacci numbers from $998999$
Two elements in a non-integral domain which are not associates but generate the same ideal
Every neighborhood of identity in a topological group contains the product of a symmetric neighborhood of identity.
$A,B,C \in M_{n} (\mathbb C)$ and $g(X)\in \mathbb C$ such that $AC=CB$- prove that $A^jC=CB^j$ and $g(A)C=Cg(B)$
Every normal subgroup of a finite group is contained in some composition series
Let $\displaystyle f$ be differentiable, $\displaystyle f(x)=0$ for $|x| \geq 10 $ and $g(x)=\sum_{k \in \mathbb Z}f(x+k).$
Can $e_n$ always be written as a linear combination of $n$-th powers of linear polynomials?
(non)equivalence of definition of non-atomic measure for finitely additive measure
Calculating the divisors of the coordinate functions on an elliptic curve
Why is sorting pancakes NP hard?

Ok, I really need some help understanding this because either my brain isn’t working at the moment or I’m breaking math and I have a striking suspicion that one of those is more likely.

Anyways, here’s my process. WolframAlpha tells me there are 12 integer solutions, they are all $^+_-n$ so let’s say there are 6 of them. They are as follows: $129, 147, 172, 196, 258, 294$

Ok, so here’s how I attempted to solve it. $n$ looks like this ${\prod_{i=1}^kp_i^{\alpha_i}}$. And $\phi(n)=n\prod_{p\vert n}(1-\frac{1}{p})$. So I plug $n$ in and get an equation like this:

- $\mathrm{lcm}(1, 2, 3, \ldots, n)$?
- Consider the relation R given by divisibility on positive integers that is xRy <-> x|y
- Deriving the formula for the Möbius function?
- Prove that two distinct number of the form $a^{2^{n}} + 1$ and $a^{2^{m}} + 1$ are relatively prime if $a$ is even and have $gcd=2$ if $a$ is odd
- Comparing $2013!$ and $1007^{2013}$
- How many digits does $2^{1000}$ contain?

$\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)=84$

Now, solving for $n$ SHOULD be equivalent to solving for $p_i, \alpha_i$, right?

So, I started going through possible values of $k$ and I’m interested in the case of $k=2$.

This means that $n$ has two prime factors, so it looks like $p_1^{\alpha_1}p_2^{\alpha_2}$, and the equation is:

$p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)=84$

Ok. Here’s my issue. Factoring $84$, we get $2\times2\times3\times7$

So I try to see a pattern. The first solution I came up with is $p_1=7, \alpha_1=2, p_2=2, \alpha_2=2$. Then I followed the same logic that led me to that solution but didn’t find any more so I concluded that the other solutions must be as higher values of $k$. But then I factored $172$ and saw that it also had only two primes. It also fits the pattern. So I realized that I could get ones in that product as a result of $p^0$ and following that pattern, filling in the remaining factors, I found the $129$ solution.

No more, the next one must be at $k=3$. NOPE. $147$ also factors into only 2 primes. So now I’m really at a miss. Is there a more effective way to iterate over all of these combinations?

- Which number was removed from the first $n$ naturals?
- Are differences between powers of 2 equal to differences between powers of 3 infinitely often?
- $4494410$ and friends
- What is the Euler Totient of Zero?
- Find the LCM of 3 numbers given HCF of each 2.
- How to show that $2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$
- Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.
- Prove that $n^{30}-n^{14}-n^{18}+n^2$ is divisible by $46410$
- Prove that none of $\{11, 111, 1111,\dots \}$ is the perfect square of an integer
- Smallest multiple whose digits are only ones and zeros

Look at 7. Two possibilities:

- $7|(p-1)$ with $p|n$:

hence $p = 14k+1 \in \{ 29, 43\}$ (the others are too big). - If $p=29$, $\phi(n) = 28\times 3 = (29-1)(3)$. 3 has to be some $(p-1)p^{a-1}$ but $p=4$ is not prime.
- If $p=43$, you have the solution $\phi(n) = 42\times 2\implies n = 43\times 3$ or

$n = 43\times 2^2$. - Otherwise: $7|n$. $\phi(n) = 6\times 7\times 2\implies n= 7^2\times 3$ or $n= 7^2\times 2^2$.

I have used that $\phi(n) = 2\implies n\in\{3,4\}$.

```
84 129 = 3 * 43
84 147 = 3 * 7^2
84 172 = 2^2 * 43
84 196 = 2^2 * 7^2
84 258 = 2 * 3 * 43
84 294 = 2 * 3 * 7^2
```

I see, you had those.

I suppose what I would emphasize is this: $\phi$ is multiplicative. So it is determined by its behavior on prime powers. Next, $\phi (p^k)$ is always divisible by $p-1.$ So, we are required to have $(p-1) | 84,$ so out of that list of numbers with $\phi(n) | 84,$

```
1 2 = 2
2 3 = 3
2 4 = 2^2
4 5 = 5
2 6 = 2 * 3
6 7 = 7
4 8 = 2^3
6 9 = 3^2
4 10 = 2 * 5
4 12 = 2^2 * 3
12 13 = 13
6 14 = 2 * 7
6 18 = 2 * 3^2
12 21 = 3 * 7
12 26 = 2 * 13
12 28 = 2^2 * 7
28 29 = 29
12 36 = 2^2 * 3^2
12 42 = 2 * 3 * 7
42 43 = 43
42 49 = 7^2
28 58 = 2 * 29
42 86 = 2 * 43
42 98 = 2 * 7^2
84 129 = 3 * 43
84 147 = 3 * 7^2
84 172 = 2^2 * 43
84 196 = 2^2 * 7^2
84 258 = 2 * 3 * 43
84 294 = 2 * 3 * 7^2
```

the primes allowed are 2,3,5,7,13,29,43, I guess that’s it. Some evident prime powers that need to be considered as alternatives to just primes. Oh, 13 does not get used, because then you need $\phi(something) = 21,$ and $\phi$ is never odd unless it is exactly $1.$ Again, 9 does not get used, i don’t think there is any number with $\phi = 14,$ don’t remember why, but people ask that here fairly often so you can find an answer on MSE.. The bit about odd is fairly easy, if there is any odd prime factor $p,$ then $(p-1)$ is even. So all that is left is powers of $2.$

- Dedekind Cuts versus Cauchy Sequences
- Finite Group with $n$-automorphism map
- Are there periodic functions without a smallest period?
- Number theory problem – show $N$ is a square when…
- Is there a systematic way of finding the conjugacy class and/or centralizer of an element?
- Questions about rank and eigenvalues of a matrix
- Prove that a UFD is a PID if and only if every nonzero prime ideal is maximal
- Difference of order statistics in a sample of uniform random variables
- Functions determine geometry … Riemannian / metric geometry?
- What are the analogues of Littlewood-Richardson coefficients for monomial symmetric polynomials?
- Correlation between three variables question
- Why does the Fibonacci Series start with 0, 1?
- Show that $\int_0^\infty\frac{1}{1+x^n}\,\mathrm dx = \frac{\pi/n}{\sin(\pi/n)}$ for $\mathbb{N}\ni n\geq 2$
- block matrix multiplication
- Dedekind's theorem on the factorisation of rational primes