Tag Info

New answers tagged

0

In general $\left\lfloor\frac{k}2\right\rfloor$ integers less than or equal to $k$ are even. Of those, half are divisible by $4$. Of those, half are divisible by $8$. Et c. So, sum the values $\left\lfloor\frac{k}2\right\rfloor +\left\lfloor\frac{k}4\right\rfloor+\cdots$ to find the total. For $500$, this means we go to $2^8$, since it is the highest power ...


0

I will add here Steven Stadnicki's comments as an answer, so the question will be closed in some days (if other answers do not come): (1) is trivially implied, as you suggest, but (2) is not trivially implied. That said, it would be very surprising if the proof of Green-Tao could not be extended to handle your case - in fact, probably even the special ...


0

You can prove very much stronger results: in increasing order of generality we have The upper Banach density of prime powers is 0. The upper Banach density of perfect powers is 0. The Buck's measure density of perfect powers is 0. The Buck's measure density of product of $n$ perfect powers is 0. All these results follow from Corollary 6 at 1.


3

The precise statement of Perron's formula is that for any $c>1$ $$\sum_{n\leq x} \Lambda(n)=\frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{\zeta'(w)}{\zeta(w)}\frac{x^w}{w}dw.$$ The reason that the lack of zeros on the $1$-line is equivalent to the prime number theorem comes from evaluating the integral by contour integration. Notice that the ...


0

This answer is a bit of a work in progress, but if $n=2^x-1$, then $$\frac{D(n)+u^2}{2}=\sum_{k=1}^{u}{\frac{2^x}{k}}$$ which can be computed as: $$ \sum_{k=1}^{u}{\frac{2^x}{k}}= \left(\sum_{i=0}^{x}{\frac{(x-i)(x-i+1)}{2}\sum_{j=2^i }^{2^{i+1}-1}{r_{j-1}}}\right) - x(x-1) $$ where $r_j$ is the sum of a row as described in ...


2

The set $C$ of natural numbers whose binary representation has an odd length has upper asymptotic density $\frac{2}{3}$. The same happens for the set $D$ of natural numbers whose binary representation has an even length. In particular $d^\star(C)+d^\star(D)=\frac{4}{3}$ while $d^\star(C\cup D)=1$. So, if we take $A=2C$ and $B=2D+1$, we have: ...


0

For sufficiently large $n$, there are always unique tuples $a,b,c, \ 0<a<b<c$ and $a',b',c', \ 0<a'<b'<c'$ such that $a+b+c=n=a'+b'+c'$ and $a \times b \times c = a' \times b' \times c'$. Proof. Say we have $b$ divisible by $3$ and $c$ divisible by $2$. This assumption will be justified later. Relate $a,b,c$ with $a',b',c'$ as follows: ...


0

We know we haven't been duped because we utilize axioms instead of writing things down explicitly. For instance, the natural numbers $0, 1, 2, \ldots$ ($\mathbb{N}$) are not constructed by writing out each integer in turn. Instead, we write out axioms: for all $x$, $x$ has a successor $Sx$; if $Sx = Sy$, then $x = y$; $0$ exists; for all nonzero $x$, $x = ...


1

Color all the points in $A$ red and color all the rest of the points blue. By Van der Waerden's Theorem, if $N = W(2, n)$, then one of these colors must have an arithmetic progression of length $n$.


5

As Lucian pointed out this follows immediately from the properties of cyclotomic polynomials. We have the factorization (into polynomials irreducible over $\Bbb{Q}$) $$ x^n-1=\prod_{d\mid n}\Phi_d(x). $$ Your observation follows from this as the factorization $$ a^n-b^n=b^n[\left(\frac ab\right)^n-1]=b^n\prod_{d\mid n}\Phi_d(\frac ab)= \prod_{d\mid n}b^{\deg ...


1

You do not need any Algebraic Number Theory to start; of course there are some problems where you would need some but at the start you rather will not encounter them. Some Analytic Number Theory seems at least very useful. As the type of questions is quite related. A book I would recommend is "Introduction to Analytic and Probabilistic Number Theory: ...


2

$$1+1=0\mod 2.$$$$1\oplus1=0.$$ With elliptic curve addition, you can have $$1+1=\infty.$$


0

Not an answer, but another point of view $\prod_{i=1}^{k}p_i^ai=\sum_{i=1}^kp_i^2=(\prod_{i=1}^{k}p_i^{ai-1})*(\prod_{i=1}^{k}p_i)$ So it's a Hurwitz equation (More complete but in French) Lets call $A=\prod_{i=1}^{k}p_i^{ai-1}$ If there is a solution, for $k\gt2$ and $p_i\neq0$, we have $1 \leq A \leq k.$ We can put some restrictions on fundamentales ...


1

The first equality is certainly true (modulo some convergence justification): \begin{align*} \sum_{n=1}^\infty \frac{f(n)}n &= \sum_{n=1}^\infty \frac1n \sum_{\substack{d\mid n \\ \sqrt n\le d \le n}} (-1)^d \\ &= \sum_{d=1}^\infty (-1)^d \sum_{\substack{d\le n \le d^2 \\ d\mid n}} \frac1n \\ &= \sum_{d=1}^\infty (-1)^d \sum_{1\le m \le d} ...


1

Note that $\gcd(a,x)=c \iff \gcd(a/c,y)=1$ where $y=x/c$. The latter equation has $\phi(a/c)$ solutions with $1\le y \le a/c$, where $\phi$ denotes the Euler phi function. This means the original equation has $\phi(a/c)$ "basic" solutions $x_0$ with $1\le x _0\le a$. All other solutions have the form $x=x_0+ka$ where $x_0$ is a basic solution. This leaves ...


2

Just use the Binomial expansion, for $(1-8)^{1/2}$. It’s a fact, not too terribly hard to prove, that $(1+4t)^{1/2}$ is a series in $t$ with all integer coefficients. Plug in $-2$ for $t$, voilà.


0

No, if $-1\equiv b^2\bmod p$, then $b$ itself generates a subgroup of order $4$ in $(\mathbb{Z}/p\mathbb{Z})^\times$, namely $$\langle b\rangle\;=\;\{b^0=1,\;\;b^1=b,\;\;b^2=-1,\;\;b^3=-b\}$$ After that, we get $b^4=(-b)\cdot b=(-1)\cdot (-1)=1$. Therefore $\langle b\rangle$ has $4$ elements. If $b$ has a square root (which need not be the case) then it ...


0

You could try programming a sieve to mark all the composites, then add up the unmarked numbers. To do that, you'll need a list of primes up to $10^7$. In order to get that, you could program a sieve... This method is obviously pretty memory-intensive, but it's certainly faster than prime-testing each integer from $10^{10}$ to $10^{14}$.


0

This is my attempt. Since the block is of size $c$, there is only one number which is divisible by $c$. Since $b<c$, there is "at least one" number (can be 1 or more) which is divisible by $b$. Again $a<b$, So for every block $b$ you choose (by dividing the $c$ block into many partitions so that each partition contains exactly one number divisible by ...


2

We will work these two at a time. Note that $(18,96)=6$ and $4\equiv52\pmod{6}$, so the first two equations are solvable. We need to solve $$ \frac{x-4}{6}\equiv\begin{bmatrix}0\\8\end{bmatrix}\text{mod}\begin{bmatrix}3\\16\end{bmatrix}\tag{1} $$ Using the Extended Euclidean Algorithm as implemented in this answer, we get $$ \begin{array}{r} ...


2

Assuming solutions in $\mathbb{N}$, this is just the problem of partitions of integers; $k_1$ is the number of 1's in the partition, $k_2$ the numbers of 2's, and so forth. I don't believe a closed-form expression for the number of partitions of a given integer exists, though recursive algorithms exist to generate all the partitions of a given integer. ...


2

Suppose there are about $f(N)$ losing points in $[1,N]$. There would be around $f(N+1)\approx f(N)+1f'(N)$ losing points in $[1,N+1]$, so $f'(N)$ is the chance that $N+1$ is a losing point. On the other hand the odds that $N+1$ is a losing point is the chance that all $N+1-a$ are composite. Pretend that the $N+1-a$ are all $O(N)$, then this chance would be ...


4

Below I've left my previous flawed approach. It is interesting that my upvoters and I hadn't noticed the highlighted mistake. And also that there exists a very straightforward proof: $$\prod_{m=1}^n\frac{p_m}{p_m-1}-\ln n>\sum_{m=1}^n\frac{1}{m}-\ln n>\gamma>0. $$ If you wish to avoid Mertens but not Rosser, note that your inequality is weaker ...


5

Assume $L$ is finite, say $\max L=m$. Then For any $n>m$ there exists $p$ with $n-p\in L$. As this implies that all prime gaps are $<n$, it is absurd. Hence $L$ is infinite.


4

We have $$\prod_{i\leq n}\frac{p_{i}-1}{p_{i}}=\prod_{i\leq n}\left(1-\frac{1}{p_{i}}\right)=\frac{1}{\log\left(p_{n}\right)e^{\gamma}}+O\left(\frac{1}{\log^{2}\left(p_{n}\right)}\right) $$ by the Mertens theorem. Now note that, by Rosser's theorem ...


0

Maple also says no: is((factorial(1992)-1)/(3449*8627), prime); $$\it{false}$$


1

I just ran a Rabin-Miller test on that number and I got the result "False" (i.e. it is NOT a prime number). If you want to know the divisors in addition to what you asked then I don't think that is computationally easy. >>> rabinmiller(a,1) False


1

yes, i think they are equivalent. If there are infinitely many twin primes, then for each $p,p+2$ we can find $n,n+2$ (just take $n=p-3$)such that your condition is satisfied, so $|T| = \infty$. Conversely, if $T$ is infinite, then for each $(n,n+2) \in T$ there is a pair of primes $p,p+2$ which is greater than $n$. So there are infinitely many of them. i ...


1

Yes, $\mathbb{C}_p\cong\mathbb{C}_q\cong\mathbb{C}$. However, the isomorphism is only an isomorphism of fields. The natural topology on the three fields are different, so they are nonisomorphic as topological fields. However, the isomorphism is impossible to fully specify using a finite number of symbols/words. Yes, for $x\in\mathbb{C}_p$, it does make ...


2

Since the GCD of the moduli is $(15,21)=3$, it is necessary that $x$ be the same thing in both equations mod $3$. That is, $$ x\equiv5\pmod{15}\implies x\equiv2\pmod{3} $$ and $$ x\equiv8\pmod{21}\implies x\equiv2\pmod{3} $$ If we didn't get that $x\equiv2\pmod{3}$ from both equations, a solution would not be possible. This prompts us to look at ...


0

When you say $x\equiv 5 \mod 15$ you are saying that $x$ is in some coset of $15\mathbb{Z}$, let's call it $15\mathbb{Z}+5=\{...,-10,5,20,...\}$. When you say $x\equiv 8 \mod 21$ you are saying that $x$ is in some coset of $21\mathbb{Z}$, that is $21\mathbb{Z}+8=\{...,-13,8,29,...\}$, and you're looking for the intersection of both cosets. The proof of the ...


2

$x \equiv 5 \bmod 15$ means that $x=5+15a$. $x \equiv 8 \bmod 21$ then means that $5+15a=8+21b$. So, you're looking for $a,b$ such that $15a-21b=3$. Here enters the extended Euclidean algorithm. We get $a=3$ and $b=2$ and so $x=50$. This solution is unique mod lcm$(15,21)=105$.


3

Suppose you have $x_n$ such that $2^n\mid x_n^2+7$. If $2^{n+1}\mid x_n^2+7$, you can let $x_{n+1}=x_n$. If not, then $$(x_n+2^{n-1})^2+7=(x_n^2+7)+2^n x_n+ 2^{2n-2}$$ is divisible by $2^{n+1}$ (as long as $n\geq 3$) since $x_n$ must be odd. So in this case, you can define $x_{n+1}=x_n+2^{n-1}$. By induction, you can thus define a sequence $(x_n)$ such ...


-1

Very similar to the Bertrand approach, except significantly more elementary. Suppose for contradiction that a partial sum of the harmonic series is an integer $z$: $$1 + \frac{1}{2} + \frac{1}{3}+...+\frac{1}{n}=z$$ Now consider the maximal power of $2$ below $n$ and let's call it $2^t$. (Note that all other integers between 1 and $n$ have a power of $2$ ...


3

You are on the right track, but a simple way is to notice that both $$ a(n) = \sum_{t\mid n}d^3(t), \qquad b(n)=\left(\sum_{t\mid n}d(t)\right)^2 $$ are multiplicative functions, so, in order to prove $a(n)=b(n)$, it is enough to prove: $$ a(p^k) = b(p^k) $$ that is equivalent to the well-known identity: $$ \sum_{j=0}^{k}(j+1)^3 = ...


0

take any integer $n> 3$, and divide it by $6$. That is, write $n = 6q + r$ where $q$ is a non-negative integer and the remainder $r$ is one of $0$, $1$, $2$, $3$, $4$, or $5$. If the remainder is $0$, $2$ or $4$, then the number $n$ is divisible by $2$, and can not be prime. If the remainder is $3$, then the number $n$ is divisible by $3$, and can not ...


3

If the solution exists, the congruence can be rewritten as $kx-a=Mj$ for some integer $j$. This implies $kx-Mj=a$. The left side is divisible by $g$. So for the equality to hold right side must also be divisible by $g$.


2

If $p \equiv 1 \pmod 4$, then $-1$ is a square mod $p$. (This is proved quickly with Euler's Criterion, among other ways). So there is some $x$ such that $x^2 \equiv -1 \pmod p$, or rather $p \mid (x^2 + 1)$. Let's consider ourselves working within the Gaussian Integers $\mathbb{Z}[i]$, which is a Euclidean Domain (since we have a division algorithm) and ...


7

The error is here: Then, since $x$ is not divisible by $a$ (because $x$ is odd, and $a$ is even), it must be: $$\sum_{i=0}^{p-1} \binom{p}{i}a^{\ p-1-i}x^{\ i} \equiv 0\;(mod\;a^{\ p-1})$$ If you write $a\sum_{i=0}^{p-1} \binom{p}{i}a^{\ p-1-i}x^{\ i} = y^p$, as you do, then we have that $a | y^p$. This does not imply that $a^p | y^p$, as $a$ is ...


0

The main thing to note is that this function you're summing over is $1$ for square-free numbers. So start out with a sum of $N-1$ (adding $1$ for every number from $2$ to $N$), and you're almost done. This solves the problem of having to know the primes up to $N$ – now we only have to deal with primes up to $\sqrt N$. Also note that $p^p$ will ...


0

Take the case $\boxed{0 < \theta < \frac12}$. Let $a = \max\{k\geq 0 \mid k\theta < 1-\theta\} = \lfloor \frac{1}{\theta} \rfloor -1 \geq 1$. Take $x \in (0,\theta)$. Then after $a-1$ iterations, $y:=T^{(a-1)} x \in ((a-1)\theta, a\theta)$. At the next iteration, $Ty$ falls in $(a\theta, (a+1) \theta) = (a\theta,1-\theta)\dot{\cup}(1-\theta, ...


0

I don't believe that is known whether infinitely many Mersenne numbers are composite, but it is generally suspected to be so.


6

We explain the reduction, and later, if questions arise, explain $\psi$. A formula $\alpha(x_1,x_2,\dots, x_k)$ is existential if it has the shape $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l),\tag{1}$$ where the formula $\beta(x_1,\dots,x_k, t_1,\dots,t_l)$ is quantifier-free. Sometimes, informally, as in the definition ...


10

The question of whether two "numbers" are "equal" is a somewhat subtle one. For example, lets work with a simpler number, namely "2". Certainly $2\in\mathbb{Z}$, but also $2\in\mathbb{Q},2\in\mathbb{R}$. Of course, they're all called the same name, and they satisfy some of the same properties: For example, in all three situations, $2 = 1+1$, and indeed one ...


-1

@frogeyedpeas Thank you for the great answer, can you give me a demonstration for solving it where A=111111111 Which is divisible by 3. Because I did not understand completly. also for the A I gave I know there is atleast 1 solution but not more than 4. Thanks for the help.


1

Unfortunately, such things are extermely hard to prove formally, because the smaller thing has a greater base. However I hope this approximation argument can help. We have $n\rightarrow n \rightarrow n \rightarrow n \approx f_{\omega2}(n)$, so if $n=a\rightarrow a \rightarrow a \rightarrow a$, then $$n\rightarrow n \rightarrow n \rightarrow n \approx ...


0

Your condition is equivalent to $$ m^2 = \frac{A^2}{3} - 3n^2 $$ Note that if m and n are integers then it must be the case that $$\frac{A^2}{3}$$ Is an integer, meaning $A^2$ is divisible by 3, meaning $A$ is itself divisible by 3. Let $t = \frac{A}{3} $ then it follows $$ m^2 = 3t^2 - 3n^2 $$ Yielding $$ m^2 = 3(t-n)(t+n)$$ So consider any ...


0

This is the base t expansion of a number, which is of course unique. Now if the polynomial factors it must factor as P*1. Since 1 has a unique base t expansion it must be that one of the polynomials is 1, hence the other is our given polynomial. So our polynomial does not factor. -M


13

No. The smallest prime factors are $3449$ and $8627$ (found with Mathematica). For what is worth: $$ \{n\in\mathbb{N}:2\le n\le2000\text{ and }n!-1\text{ is prime }\}=\\\{3,4,6,7,12,14,30,32,33,38,94,166,324,379,469,546,974,1963\} $$ Should have thought checking OEIS. This is secuence A002982


1

As imple algorithm such as the following may be suitable for not too large positive integer inputs $n$: Let $a\leftarrow 1$, $b\leftarrow 1$ While $4\mid n$, let $a\leftarrow 2a$ and $n\leftarrow n/4$ If $2\mid n$, let $b\leftarrow 2b$ and $n\leftarrow n/2$ Let $p=3$ While $p^2\mid n$, let $a\leftarrow pa$, $n\leftarrow n/p^2$ If $n<p^2$, let ...



Top 50 recent answers are included