Need some help on this question from Victor Shoup Let $\tau(n)$ be the number of positive divisors of $n$. Show that: $\sum_{d\mid n} \mu(d)\tau(n/d)=1$; $\sum_{d\mid n} \mu(d)\tau(d)=(-1)^r$, where $n=p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorization of $n$. I have tried both of them but cant find any solution!We have to use Mobius Function properties to prove […]

Show that the positive integral multiples of $2^{n}-1$ when expressed in binary will have at least $n$ ones’. My work so far: Let $b(k)$ be the number of ones when k is expressed in binary and let $e(n)$ be the number of factors of 2 dividing $n$. I found that $$b(n-1)=b(n)+e(n)-1.$$ So i know that […]

Suppose, a Mordell curve $$y^2=x^3+k$$ has at least one integral solution. Denote $d$ to be the smallest absolute value of $x$, such that $x^3+k$ is a square, in other words, $d$ is the the smallest possible absolute $x$-coordinate of an integral solution. Is any reasonable upper bound for $d$ depending on $k$ known ? In […]

Show that $\sum_{d \mid n} \mu(\frac{n}{d})\nu(d) = 1$, for any positive integer n. Where $\mu$ denotes the Mobius function defined by $\mu(n)=(-1)^{s}$ if $n=p_{1} \dotsc p_{s}$ for distinct primes $p_{1} \dotsc p_{s}$ and $\mu(n)=0$ otherwise, and $\nu(n)$ denotes the number of divisors of $n$. I think I have to apply the Mobius Inversion Theorem somehow […]

The problem on which I am currently stuck is, Is it true that, $$x+y< \dfrac{p_{\pi(x)}+p_{\pi(y)}+p_{\pi(x)+1}+p_{\pi(y)+1}-2}{2}$$ for all sufficiently large $x$ and $y$, $x+y$ is a prime and $\pi(x)$ is the prime counting function? My Atempt I tried to prove the problem by showing that $$x<\dfrac{p_{\pi(x)}+p_{\pi(x)+1}-1}{2}$$and $$y<\dfrac{p_{\pi(y)}+p_{\pi(y)+1}-1}{2}$$ But I cannot prove or disprove it by any […]

I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this? I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots F_{n-1}+2$, but I can’t see how I can apply this to my problem. What am I missing?

Recently I have been reading this post and I have noted something significant in the fake argument. As one can easily see that the basic idea behind the argument had been to show that the sequence $x_n=\dfrac{\pi(n)\ln n}{n}$ is strictly decreasing for all $n$. But, notice that the Prime Number Theorem is equivalent to the […]

Since it is not easy to determine the integral points of a Mordell curve $$y^2=x^3+n$$ with integer $n\ne 0$, I came to the following questions : $1)$ What is the smallest (in absolute value) integer $n$ , such that it is unknown whether the Mordell-curve $y^2=y^3+n$ has an integral point ? $2)$ What is the […]

Is there an efficient algorithm (maybe Polynomial-time?) for factorizing Mersenne numbers of the form $2^p – 1$? We can assume that $p$ is a prime because if it is not, then we can reduce the problem to factorizing smaller Mersenne numbers in polynomial time. I understand that there is a more efficient primality test for […]

Let $a_n$ be a strictly increasing sequence of natural numbers such that $$\lim_{n\to\infty}\frac{a_n}{2^n}=0.$$ Now, define $$ l_n=\frac{lcm(a_1,a_2,…,a_{n-1})}{a_n}.$$ My question is: From the definition of $a_n$, can we say that $l_n\to\infty$? While I haven’t been able to find any previous work answering this question, a similar question proves that the least common multiple of a random […]

Intereting Posts

solve $\sin(z)=-1$ in the set of complex numbers
Proof that if $s_n \leq t_n$ for $n \geq N$, then $\liminf_{n \rightarrow \infty} s_n \leq \liminf_{n \rightarrow \infty} t_n$
Most natural intro to Complex Numbers
Generalized Holder Inequality
Prove that if $A$ is an infinite set then $A \times 2$ is equipotent to $A$
Finding a Particular Coefficient Using Generating Functions
Why is continuous differentiability required?
Show that are logically equivalent
Why is polynomial regression considered a kind of linear regression?
Question about Euler's approach to find $\sum_{n=1}^\infty\frac1{n^2}=\frac{\pi^2}6$
Active and passive transformations in Linear Algebra
Functional equation: $f(f(x))=k$
Prove that there exists bipartite graph with this degree sequence: $(3,3,3,3,3,5,6,6,6,6,6,6,6,6)$
Trace minimization when some matrix is unknown
Rank of an interesting matrix