Tag Info

New answers tagged

1

We write this as $$\sum_{p\le x}{\log n\over n^\alpha}\cdot 1_p$$ From here we use partial summation to get $$\pi(x){\log x\over x^\alpha}-\int_1^x\pi(t){1-\alpha \log t\over t^{1+\alpha}}\,dt$$ using the PNT and monotonicity of the integral, this is asymptotic to $$x^{1-\alpha}-\int_1^x {1-\alpha\log t\over t^\alpha\log t}\,dt$$ This gives ...


0

If $n=2^{1000000}-1,$ then the highest number in the first ascending sequence is $2*3^{1000000-1}-1.$ Then your question becomes: when one iterates beyond that number, are there any higher numbers.


0

We can say that if $n$ is $2^n$ it is $n+1$. Of course this is a rather cheap answer, we can say a lot of stuff like that about special numbers (Like numbers of the form $\frac{2^n-1}{3}, or other numbers which we can obtain working backwards). Of course we cannot say anything just knowing the size of $n$, since this would essentially be the same as proving ...


3

The prime number theorem says that the $n$-th prime is $p_n \sim n \log n$. So your sum becomes $$ \sum_{p\le x}\frac{1}{p^{\alpha}} \sim \sum_{n : p_n \le x}\frac{1}{n^\alpha (\log n)^\alpha}\sim\sum_{n=2}^{x/ \log x}\frac{1}{n^\alpha (\log n)^\alpha} \sim \int_{2}^{x/\log x}\frac{dn}{n^{\alpha}(\log n)^\alpha} \sim \frac{n^{1-\alpha}}{(1-\alpha)(\log ...


0

Isn't this just a graphical representation of the Sieve of Eratosthenes, published "Introduction to Arithmetic" (60–120 AD) by Nicomachus...?


3

I would recommend a series of books, specifications, libraries and CAS programs. Books A Course in Number Theory and Cryptography, Neal Koblitz (very dense, but an amazing book) An Introduction to Mathematical Cryptography, Jeffrey Hoffstein, Jill Pipher, J.H. Silverman (very readable and excellent book, which is more up-to-date) An Introduction to ...


0

Yes, if $p$ is a prime number then $\phi(p^x)=p^{x-1}(p-1)$, so for $p=2$ we have $\phi(2^x)=2^{x-1}(2-1)=2^{x-1}=\frac{1}{2}\times 2^x$.


0

You will want to induct on the number of prime factors of n. Since $\phi(1) = 1$, the result holds when $n = 1$. If $n$ is prime, then $\sum_{d|n} \phi(d) = \phi(1) + \phi(n) = 1 + (n - 1) = n$. For the inductive step, suppose that $n$ has more than one prime factor and the result holds for all positive integers whose number of prime factors is less than the ...


2

I figured out an argument that works for $\left\{\dfrac{x}{2}\right\} > \dfrac{1}{2}$ $$\log\Gamma(x) \le \log\Gamma(x + 1 - \left\{ x\right\}) = \log\Gamma(\left\lfloor x\right\rfloor + 1) = \log\left\lfloor x\right\rfloor!$$ $$2\log\Gamma(\dfrac{x}{2} + \dfrac{1}{2}) \ge 2\log\Gamma(\dfrac{x}{2}+1 - \left\{\dfrac{x}{2}\right\}) = ...


1

The only numbers with exact $2$ proper divisors are the numbers of the form $p^2$, where p is a prime. The proper divisors are $1$ and $p$ in this case, and $p+1$ with $p$ prime can only be a perfect square for $p=3$. This follows from the equation $p=a^2-1=(a-1)(a+1)$. If $a>2$ , then $p$ cannot be a prime. So, there is only $1$ case of $2$ ...


1

Yes this is proved by S.W.Golomb. I cannot resist to show a piece of my work:http://arxiv.org/abs/1311.1398


0

No. Let $a_i=0.99$ for all $i$ and $t=6$. Then $k=5$. But if $ A_j \subseteq \lbrace 1,\ldots,t \rbrace $ with $ \sum_{i \in A_j} \lbrace a_i \rbrace \ge 1 $ then $|A_j|\ge 2$, so there can be at most $3<4=k-2$ such mutually disjiont subsets. PS. Instead of fractional parts we can simply consider the rational numbers $a_i\in (0,1).$


2

First, recall that $x^m-p$ is always irreducible over $\mathbb{Q}$ for $p$ prime (via Eisenstein's criterion). Consider the field $\mathbb{Q}[\sqrt[n]{7},\sqrt[n+3]{7}]$. It contains $\mathbb{Q}[\sqrt[n]{7}]$ and $\mathbb{Q}[\sqrt[n+3]{7}]$ so its dimension is divisible by $n$ and $n+3$. They are coprime (since $3\nmid n$) so the dimension is at least ...


1

In my comment, I said there was an argument from compactness, but on thinking a little more, I realized that since the set of irreducible polynomials over the ring of integers $\mathfrak o$ of your field is not closed, that approach would be a little trickier than I hoped. Instead, let’s do it piecemeal; I’m sure there’s a quicker argument than what I give ...


1

Here is one way to do the calculation: \begin{align*} \frac{\sum_{m=0}^{i-1}\binom{s}{m}(p-1)^{k-1-m}}{\sum_{m=0}^{i}\binom{s}{m}(p-1)^{k-1-m}}&= \frac{\sum_{m=0}^{i-1}\binom{s}{m}(p-1)^{-m}}{\sum_{m=0}^{i}\binom{s}{m}(p-1)^{-m}}\tag{1}\\ ...


1

If I understand correctly the question is to find for which values of $n,k$ we have that $\binom{n}{k}$ is a multiple of $2,3,5$ In general you can figure out if $\binom{n}{k}$ is a multiple of any prime $p$ using Kummer's theorem, to do this write $n$ and $k$ in base $p$. If each digit in the expression of $n$ is larger than or equal to the respective ...


1

If $m\mid a$ and $m\mid b$, then $m$ is a common divisor of $a$ and $b$. By definition $\gcd(a,b)$ is the largest common divisor of $a$ and $b$, so $\gcd(a,b)\ge m$.


3

(Updated with more info.) As pointed out by E. Schmidt, the sequence A023042 shows that a large percentage of $N^3$ are a sum of three positive cubes. OEIS lists only $N<1770$, but we can extend that: $$\begin{array}{|c|c|} N&\text{%}\\ 2000&85.8\text{%}\\ 4000&89.8\text{%}\\ 6000&92.1\text{%}\\ 8000&93.3\text{%}\\ ...


1

I believe that the only subset that works is $\{1,2,3,4,\dots\}$. (There are no $a$'s not in the set, so it satisfies the condition vacuously.) Reason: First, notice that $1$ has to be in the set. Now, consider, what if $n$ was missing from the set? Call one of its prime factors $p_n$. Now, if $n$ was missing, that would mean that there are exactly $n$ ...


0

Do you want only $a$ numbers to exist or at least $a$ numbers? Because if it is latter then how about $A$ be the set of primes.


1

The same idea also gives $p_n\leq 4^n$ and a rather trivial improvement of that is: $n\in\Bbb Z_+,\;1\leq x\leq p_n\implies x=p_1^{e_1}\cdots p_n^{e_n}\cdot m^2,\;e_i=0,1\wedge\;m^2<p_n$. If $e_n=1$ then $0=e_1=\cdots=e_{n-1}$ and if $e_n=0$ there is at most $2^{n-1}$ ways to chose $x$. Similar to Erdős proof $p_n\leq(2^{n-1}+1)\sqrt p_n$ which gives ...


0

First, also from the reciprocity law, we know that $\;x^2=z\pmod{2^k}\;$ , has a solution for $\;k\ge 3\;$ iff $\;z=1\pmod 8\;$, which is the case here. Now: $$x_k^2=z\pmod{2^k}\implies x_{k+1}=\begin{cases}x_k+2^{k-1}&,\;\;\frac{x_k^2-z}{2^k}=1\pmod 2\\{}\\x_k&,\;\;\frac{x_k-z}{2^k}=0\pmod 2\end{cases}$$ and you can check easily $\;x_{k+1}\;$ is ...


2

Note that $\ell(x)$ is an exceptionally slow-growing increasing function, and never increases by more than $1$, so the sequence $(n+\ell(n))_{n\in\Bbb N}$ increases in steps of $1$ and occasionally $2$, and so already almost all numbers are covered except those skipped over in the gaps when it increases by $2$. These are the points at which $\ell(n)$ ...


0

Hint : for $m=1$, by induction on $n$ we have, $f(1,n)\not\in\mathbb{N}$. suppose that for every $n\in\mathbb{N}$, $f(k,n)\not\in\mathbb{N}$ then for $m=k+1$ we have : $$\forall n\in\mathbb{N},\qquad\displaystyle \frac{3^{k+1}(2^n+1)-2^{k+1+n}}{2^{k+1+n}-3^{k+2}}\not\in\mathbb{N}$$ because, by induction on $n$, if $f(k+1,l+1)\in\mathbb{N}$, then we have : ...


0

The general rule is that $(d,m)$ of positive integers can be the pair of the highest common factor $\def\hcf{\operatorname{hcf}}\def\lcm{\operatorname{lcm}}d=\hcf(a,b)$ and lowest common multiple $m=\lcm(a,b)$ of two positive integers $a,b$ if and only if $d~$divides$~m$. The the condition is necessary is because $d$ must divide $a$ which must divide $m$, by ...


0

This is a comment, not an answer, but the comment space is too small to hold this. I proved this result on representation in general bases over 40 years ago: Let $\mathbb{B} =(B_j)_{j=0}^{\infty}$ be an increasing series of positive integers with $B_0 = 1$. A positive integer $n$ is represented in $\mathbb{B}$ if $n$ can be written in the form $n = ...


0

I will do the case for $n=m$ since graydad has done the work for n>m WLOG. Let $A=\sum_{i=0}^na_ik^i$ and $B=\sum_{i=0}^mb_ik^i$. If A=B, then We should have $A-B=B-A=0$. $A-B=$[$a_nk^n+a_{n-1}k^{n-1}+...+a_0$]$-[b_nk^n+b_{n-1}+...+b_0]$$=$$(a_n-b_n)k^n+(a_{n-1}-b_{n-1})k^{n-1}+...+(a_0-b_0)=\sum_{i=0}^n(a_i-b_i)k^i$. If $∀i$ $(a_i-b_i)<0$, then ...


3

The answer key is correct that $60$ cannot be the LCM, but incorrect if it claims that $12$ can be the LCM. If the HCF of $a$ and $b$ is $8$, the LCM is $\frac {ab}8$ and since $8$ divides both $a$ and $b$ it divides the LCM.


4

You are correct that both 12 and 60 cannot be the least common multiple of two numbers whose highest common factor is 8. There's probably a typographical error in your text.


2

First it should be denoted $\mathbb Z_n^\times$. The units (elements which have a multiplicative inverse) in the ring $\mathbb Z_n$ are a (multiplicative) group. It consists of the congruence classes modulo $n$ of integers which are coprime with $n$. The squares are – well… the squares of these elements. Here is an example: $\mathbb ...


2

The group $\mathbb{Z}_n^{\ast}$ denotes the multiplicative group of invertible residue classes modulo $n$, that is those generated by elements relatively prime to $n$. The squares in this group are just the elements that you get considering $a^2$ for $a \in \mathbb{Z}_n^{\ast}$. For context, note that one says that an element $x$ is a quadratic residue ...


2

Here's one I read a number of years ago that works mod $p$ for every prime $p$. I don't know if it works for $\mathcal{O}_p$. Let $f(x) =(x^2-2)(x^2-3)(x^2-6) $. $f$ obviously has no rational roots. If $x^2-2$ and $x^2-3$ have no roots mod $p$, then 2 and 3 are not quadratic residues mod $p$, so 6 is a quadratic residue mod $p$, so $x^2-6$ has a root.


0

For every $n$, there is at least one solution, namely, $$1+1+\cdots+1+2+n=1\times1\times\cdots\times1\times2\times n$$ where the number 1 appears $n-2$ times. Now suppose $n=rs$ with $2\le r\le s$. Then $$1+1+\cdots+1+(r+1)+(s+1)=1\times1\times\cdots\times1\times(r+1)\times(s+1)$$ where the number 1 appears $n-1$ times, so $a(n+1)\ge2$. So, if $a(n+1)=1$, ...


5

In this paper is mentioned $3x^3+4y^3+5z^3=0$, referred to there as 'Selmer's example' http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/selmerexample.pdf


11

With respect to your question if there is, for each $k$, an $n$ such that $\dfrac{n}{\pi(n)}=k$ I think the answer is affirmative. If we consider the function $f(x) = \dfrac{x}{\pi(x)}$, we can prove that $\displaystyle\lim_{x\to +\infty}f(x)=+\infty$ (by the prime number theorem or by more elementary bounds). If $f$ were continuous, as $f(2) = 2$, we should ...


1

Let's denote $g$ the image in $ \mathbb{F}_p[x_1, \dots, x_n]$, which is still a form of degree $r' < n$, with $r'\leq r$. Now let $V$ the set of zero of $g$ in $(\mathbb{F}_p)^n$. As $(0,\ldots,0)$, $Card(V)\geq 1$. Set $P = 1-g^{p-1}$ and let $x\in (\mathbb{F}_p)^n$. If $x\in V$ you have $P(x)=1$, and if $x\not\in V$, $g(x)$ is not zero, so that ...


3

if $p\ge 3$ be prime number,then $n\ge 3$,and $$n(n^2-1)(n^2+1)=p^4(p^4-1)$$ Note $$\gcd{(n,n^2-1)}=\gcd{(n,n^2+1)}=1,\gcd{(n^2-1,n^2+1)}=1\textbf{or}2$$ then have $$n^2+1\ge p^4$$ so $$p^4(p^4-1)=n(n^2-1)(n^2+1)\ge n(p^4-2)p^4$$ $$\Longrightarrow p^4-1\ge n(p^4-2)>2(p^4-1)$$ a contradiction On the other hand,if $p=2$,then we have ...


3

You are beginning with a global field $K$ of char. $p$, containing $\mathbb F_q$ as its maximal finite subfield, and forming the (everywhere unramified) extension $L = \mathbb F_{q^m} \otimes_{\mathbb F_q} K.$ If $\mathfrak p$ is a prime of $K$, with residue field $\kappa(\mathfrak p)$, then the primes $\mathfrak q$ of $L$ over $\mathfrak p$ correspond to ...


1

There's only on residue class with exactly one square root: 0. All other classes have two square roots or none, as $\mathbf F_p$ is a field and if $b^2=a$, then also $(-b)^2=a$. Whether a residue class has a square root modulo $p$ can be determined with Gauß's law of quadraric reciprocity.


2

It ask for which residue classes $a+pZ$ there is a unique $b+pZ$ such that $(b+pZ)^2=a+pZ$. $pZ$ is the only residue class with that property because suppose other $a+pZ$ had that property, then $(b+pZ)^2=a+pZ$ but also $(-b+pZ)^2=a+pZ$ and $b+pZ\neq -b+pZ$ because $p>2$.


1

The residue classes modulo $p$ are the elements of the quotient ring (in this case it is even a field) $R=\mathbb Z/p\mathbb Z$. So a residue class has the form $c+p\mathbb Z$ which is normally just written as $\overline{c}$ or even $c$. So a squareroot of $c$ is an element of $r\in R$ such that $r^2 \equiv c$. (That means that their residue modulo $p$ is ...


2

I'll copy part of my (not really mine, but I found it) answer from here: Does this inequality hold true, in general? I did a Google search for "density of euler phi function". The second link is http://www.ams.org/journals/proc/2007-135-09/S0002-9939-07-08771-0/S0002-9939-07-08771-0.pdf. This paper, by ANDREAS WEINGARTNER, is titled "THE DISTRIBUTION ...


4

Suppose we want to factor $P(X)$ over $\mathbb{F}_p$ for an odd prime $p$. Since $P$ is monic of degree $2$, $P$ factors if and only if $P$ has a root in $\mathbb{F}_p$. Now notice that $$ x^2 -x + 2 = 0 \iff 4x^2-4x+8=0 \iff (2x-1)^2 = -7 $$ in $\mathbb{F}_p$. Since $x \mapsto 2x-1$ is bijective on $\mathbb{F}_p$ for odd $p$, the polynomial $x^2-x+2$ has ...


2

Here are two suggestions as hints. If $x^2-x+2\equiv (x-a)(x-b)\bmod p$ then $x=a$ and $x=b$ will make $x^2-x+2$ divisible by $p$. For small primes you can just try every possible value of $a$ and $b$. You can also complete the square. Take $17$ as an example prime (because it isn't one of yours) $$x^2-x+2\equiv x^2+16x+2 = (x+8)^2-62\equiv(x+8)^2+6 \bmod ...


1

I was actually going to ask the same question... and in particular if the result would follow as the consequence of any hard, still open conjecture. From the MO thread mentioned by lhf (not the same as the one mentioned by mixedmath) I found out that Schanuel's conjecture would imply it. On the Mathworld page for $e$ there's a bit of info on numerical ...


3

You could check this by brute force. There are only ten cases to check. For instance: $$0^5 \equiv 0 \mod 10$$ $$1^5 \equiv 1 \mod 10$$ $$2^5 = 32 \equiv 2 \mod 10$$ $$3^5 = 243 \equiv 3 \mod 10$$ $$4^5 = 1024 \equiv 4 \mod 10$$ etc. It's not a slick way to prove it, but it works if you can't think of anything else.


1

By Fermat's little theorem, $$x^5\equiv x\pmod 5$$ But $x^5\equiv x\pmod 2$ is obvious by checking the even/odd case, therefore $$x^5\equiv x\pmod{10}$$


3

Here is an induction proof, since that's what you're trying to do. The base case is $1^5\equiv 1$, which is obvious. Assume $n^5\equiv n$. Now we have $$ (n+1)^5=n^5+5n^4+10n^3+10n^2+5n+1\\ \equiv n + 1+5(n^4+n) +10(n^3+n^2)\\ \equiv n+1+5n(n^3+1)\\ \equiv n+1 $$ We have $5n(n^3+1)\equiv 0$ since it's $5$ times an odd number times an even number (either $n$ ...


4

We are to prove that $x^5-x$ is divisible by 10. Also $x^5-x=x(x^4-1)=x(x-1)(x+1)(x^2+1)$, therefore it is the product of two consecutive numbers, $x(x-1)$, hence divisible by $2$.(recall product of $r$ consecutive numbers is divisible by $r!$) also, $n^p-n$ is divisible by a prime $p$ (Fermat's little theorem). Plug $p=5$ to show it is divisible by $5$. ...


1

For question b), there is 1,1,2,2,2,2,2,2...



Top 50 recent answers are included