Tag Info

Hot answers tagged

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


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 ...


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 ...


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 ...


5

It is not possible to give a finitary proof of this fact. Consider, for instance, the statement that all Goodstein sequences terminate. This is an arithmetic claim, it is independent of $\mathsf{PA}$, and it is equivalent to the claim that some (very specific) computable non-increasing sequences of polynomial towers stabilize. Instead of Goodstein ...


5

Hint: Exepted for 2 and 3, primes are always congruent to 1 or 5 mod 6. To prove this, we see that if it is 0,2,4 mod 6, it is divisible by 2, and if its 3 mod 6 its divisible by 3.


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

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 ...


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 ...


4

It is easy to show that if $n$ and $\sigma(n)$ are both odd, then $n$ is a square; and that $\sigma(n)/n$ is equal to the sum of the reciprocals of the factors of $n$. From the latter it follows immediately that $$\hbox{if}\quad m\mid n \quad\hbox{then}\quad \frac{\sigma(m)}{m}\le\frac{\sigma(n)}{n}\ .$$ Now suppose that $$\frac{\sigma(n)}{n}=\frac53\ ...


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$.


3

Let $a_n=2^{2^n}+3$. Then $a_{n+1}=(a_n-3)^2+3 = a_n^2-6a_n+12$. Since: $$ p(x)=x^2-6x+12 \equiv (x-1)(x+2) \pmod{7} $$ maps $0$ to $5$ and $5$ to $0$, we have that $7\mid a_n$ iff $n$ is odd, since $a_1=7\equiv 0\pmod{7}$.


3

Your argument for the case $p=2$ works, but it can be simplified: By Eisenstein, any polynomial $$X^n+2, \, n>2$$ is irreducible and gives rise to a field extension of degree $n$. In the case $p\neq 2$ we have to be careful: Just choosing quadratic non-residues is not enough for higher powers, since for example $3$ is a quadratic non-residue $\bmod 7$, ...


3

Your proof for $p=2$ certainly works, though the key is Eisenstein. You don't need to show that $X^{2n}-2$ has no roots (that wouldn't be enough anyway to prove what you want). In general for arbitrary $p$, note that $X^n-p$ is Eisenstein in $\mathbb{Q}_p$, and so its irreducible. By varying $n$ you find that $\mathbb{Q}_p$ has algebraic field extensions of ...


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 = ...


3

Here is attempt to answer most of the questions raised: Is it true that $f(2k)=f(2k+1)$? This seems to be true, it would suffice to prove that $2|f(n)$ for all $n$. All algorithms to cover consecutive integers with multiples of primes use at a given moment all "small" primes, so they use in particular the prime $p=2$. However this does not prove that ...


3

Let's define for $k\geq 1$ the numbers $a_k$ and $b_k$ with \begin{align*} a_k&=\underbrace{111\ldots 1}_{k}\,\underbrace{333\ldots 3}_{k}\,\underbrace{555\ldots 5}_{k}\,\underbrace{777\ldots 7}_{k}+1\\ b_k&=\underbrace{111\ldots 1}_{k}\,\underbrace{222\ldots 2}_{4k} \end{align*} Since $\underbrace{999\ldots9}_{k}=10^{k-1}-1$, OPs question can be ...


2

If $p$ is a prime, then $\sigma(p^{2n}) = 1+p+p^2+\cdots +p^{2n}$ is a sum of $1$ plus $2n$ numbers of the same parity and so is odd. Since $\sigma$ is multiplicative, $\sigma(p_1^{2n_1} \cdots p_m^{2n_m})=\sigma(p_1^{2n_1}) \cdots \sigma(p_m^{2n_m})$ is the product of odd numbers and so is odd.


2

Note: This is only a proof sketch. I omitted some details which are not really technical and you can verify it by your own. If there are some mistakes please tell me. Let us assume that $$a^2b-c=2^p,\ b^2c-a=2^q,\ c^2a-b=2^r$$ and within them $r$ is the smallest. To simplify the discussion I further assume here 'powers of $2$' means that $p,q,r>0$ (or ...


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

Because $f(x)=0$ implies $f(\sigma x)=0$ when $f$ has coefficients in $\mathbb Q$.


2

$\zeta^{m_1}$ and $\zeta^{m_2}$ are conjugate if and only if there exists $g \in \text{Gal}(F(\zeta)/F)$ such that $g(\zeta^{m_1}) = \zeta^{m_2}$. This is the case if and only if there exists $g \in \text{Gal}(F(\zeta)/F)$ such that $\chi(g)m_1 = m_2$, which happens if and only if $m_1$ and $m_2$ lie in the same coset of $\text{Im}\,\chi = S$ in ...


2

Since $\phi(25)=20$, we have: $$ 4^{999}\equiv 4^{-1}\equiv 19\pmod{25} $$ while obviously $4^{999}\equiv 0\pmod{4}$, hence by the Chinese theorem: $$ 4^{999} \equiv 44\pmod{100}. $$


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

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 ...


2

A theorem of Schinzel and Tijdeman from 1976 implies that if $P(x)$ is a polynomial with integer coefficients and at least two distinct (complex) roots, then there exists an effectively computable constant $d_0$ such that the equation $P(x)=y^d$ has no solutions with $|y|>1$ and $d > d_0$. This answers your question in the affirmative provided one ...


2

AFAIK the least multiple of any positive integer $x$ is $x$ itself. As $y^4$ is greater than zero, $x-y^4$ is less than $x$, so it can't be a multiple of $x$ (whether common with $y$ or not...). Of course that holds unless you allow ZERO as a multiple, in which case $x-y^4 = 0$ would give solutions.


2

If there is a prime greater than $n$ and at most $nm-2$, it divides the left side but not the right side. Bertrand's hypothesis almost gives this to you.


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 ...


2

We have $341=11\cdot 31$, so we have to prove that both $31$ and $11$ divides $2^{340}-1$ We know that : $11$ divides $x^{10}-1$ for every $x$ coprime to $11$, let's take $x=2^{34}$, hence $11$ divides $2^{340}-1$ Using the same argument $31$ divides $2^{30*11}-1$ for every and we know that: ...



Only top voted, non community-wiki answers of a minimum length are eligible