Tag Info

New answers tagged

2

Yes, since $n \ge 2, 2^n-1 \equiv -1 \pmod 4$.


0

$2^{2n+1} - 1 \equiv 1 \pmod 3$ is true for all odd numbers $2n + 1$. $2^{2n+1} \equiv 2 \pmod 3$ $2^{2n} \equiv 1 \pmod 3$ $4^n \equiv 1^n \equiv 1 \pmod 3$ Alternatively, you could show the cyclic pattern of the powers of two $\pmod 3$: $1, 2, 1, 2, 1, 2, \dots$, so it's clear that $2^k \equiv 1$ for $k$ even and $2$ for $k$ odd.


3

If $p$ is an odd prime, and more generally if it is an odd number, then $2^p-1\equiv (-1)^p-1\equiv -2\equiv 1\pmod{3}$. The Mersenne prime $3$ is not of the form $3n+1$.


3

Every number of the form $2^{2n+1}-1$ is of such form, because $$2^{2n+1}-2\equiv2\cdot(4^n-1)\equiv2\cdot(1^n-1)\equiv0\ \ (\text{mod}\,3)$$ And because every prime except $2$ is odd, it's true for every Mersenne prime except the first.


1

Step 1: Note that the prime powers do not contribute very much, and show that that $$\psi(x)=\theta(x)+O\left(\sqrt{x}\log x\right).$$ From this and the assumption that $\psi(x)-x=O(\sqrt{x}\log^2 x)$, it follows that $$\theta(x)-x=O\left(\sqrt{x}\log^2 x\right).$$ Step 2: Use partial summation to prove that $$\pi(x)-\text{li}(x)=\frac{\theta(x)-x}{\log ...


1

As noted by Potato, the first thing to notice is that the intersection of two subgroups, $\langle g\rangle $ and $\langle h\rangle$ is a subgroup of $G$, but moreover, it is also a subgroup of both $\langle g\rangle$ and $\langle h\rangle$. A cyclic group of prime order, such as $\langle g\rangle$ only has two subgroups $\langle 1 \rangle$ and $\langle ...


1

The additive equivalent would be to increment the n-th base b digit when you see the n-th character, with b chosen larger than the largest exponent you expect. So add $b^{25}$ when you see z, with $b\ge11$ if you expect some letter might appear 10 times. But $11^{25}>101^{10}$ so this might not be good for your use case!


0

Take any odd prime number $p$. Let $a$ be the greatest power of $2$ which divides $p-1$, and $b=\cfrac {p-1}a$ then $ab+1=p$ and $(a,b)=1$. You can do the same for $ab-1$ by taking factors of $p+1$. Since $p$ was arbitrary, and there are infinitely many primes, there are infinitely many pairs $(a,b)$ satisfying your criterion.


0

The statement is trivial from the infinitude of primes. If $p$ is prime, let $a=p+1$ and $b=1$, then $ab-1$ is prime.


1

You know that $$82!=82\times 81\times 80\times \dots \times 3\times 2\times 1$$ What is the greatest prime factor? Well first, we can find the biggest prime number in the expansion of $82!$. That prime is $79$. Is there another prime factor greater than that? I can tell you that any factors greater than $79$ are composite numbers. $80=2\times 40$, ...


1

I'd suggest using the following theorem: $$ \psi_1(x) = \frac{1}{2\pi i} \int_{c - i\infty}^{c + i\infty} \frac{x^{s + 1}}{s(s+1)} \left( \frac{-\zeta'(s)}{\zeta(s)} \right) \mathrm{d}s$$ where $c > 1$. A proof of this equality can, for example, be found in Complex Analysis by Stein and Shakarchi. It is on page 191 being proposition 2.3 of chapter 7. ...


1

Maybe you can try proving $$ (1^s+2^s+3^s+\dots)=(1^s+2^s+2^{2s}+\dots)(1^s+3^s+3^{2s}+\dots)(1^s+5^s+5^{2s}+\dots)\dots $$ for $s$ such that the series converge. The left side is $\zeta(-s)$, the factors on the right side are geometric series. I think your result will be a well-known formula. But there are analytic continuations for all of these to other ...


1

The statement is false -- although it holds for quite some time. If $c_t(n)$ denotes the number of $t$-primes smaller than or equal to $n$, we have $$c_2(1279789)<c_3(1279789)$$ and also $$c_1(58)<c_2(58)$$ (the latter wasn't part of the conjectured series of inequalities, though). Based on a quick non-rigorous reasoning (which could be wrong, of ...


8

For $k\ge 1$ we have $$2^{10^k}+1=(2^{2\cdot 10^{k-1}})^5+1=(2^{2\cdot 10^{k-1}}+1)(\dots)$$ In particular your number $n$ is not a prime.


0

Several individual mathematicians have proposed as rewards and/or incentives for the solution of various conjectures moderate or insignificant sums of money, and even rather exotic objects. The late Paul Erdős was (also) famous for the former, and Barry Mazur awarding Per Enflo a live goose (see the details on the link) is an example of the latter. In a ...


0

One reason is that there are probably no more Fermat primes! If you picked a random odd number near $2^{2^n}$ the chance that it would be prime is roughly $1/\log(2^{2^n})$ or $k/2^n$ for some constant $k$. The sum of $k/2^n$ converges, so there should be finitely many primes. The sum over all $n$ such that it is not known whether $2^{2^n}+1$ is prime or not ...


0

There are about $\frac{x\log\log x}{\log x}$ 2-primes up to $x$ and about $\frac{x(\log\log x)^2}{2\log x}$ 3-primes up to $x$, so the crossover should happen roughly when $\log\log x=4$ which is $e^{e^4}\approx2^{78.8}.$


1

This approach will not work since Dusart's bounds are not strong enough to prove that inequality. His bounds have error $n/\log^k n$ but you need closer to $\log^2 n$ to be able to prove Firoozbakht's conjecture. It's easy to see that your inequality will fail for large $n$. Multiply by $n\log n+n\log\log n$ (which is positive in this range) to get $$ ...


0

$n!+2, n!+3, n!+4, ..., n!+n$, or using product of prime called a primoral $p_n$#$ = 2*3*5*...*p_n$ another smaller gap can be found of similar size. $ p_n$#$ + 2, p_n$#$ + 3, p_n$#$ + 4, ..., p_n$#$ + p $. Now all you have to do is let n go to infinity.


0

Looking for "prime partitions" might help to find prior information for this conjecture. Another conjecture would be the sum of the gaps of consecutive primes, $g_n = p_{n+1} - p_n$: $$s = \sum_{i=1}^{n}g_i,$$ having an infinite number of primes. Considering the fact that the next prime is $p_{n+1} = s + 2$ one might think it be easy, but it is not.


2

Both identities can be proved directly, without reference to the prime number theorem or the Riemann hypothesis or each other. So there's no circularity.


0

Since $(a^2)^{3N}\neq a^2$ if $a\neq 1$, it is obvious that the statement cannot hold for arbitrary values of $p$. For example, taking any $p>(a^2)^{3N}$ will provide a counterexample.


1

A counter example: I assume that N is a generic natural number and p is any prime number. Let's say $N=2 , p=7$ $a=2$ $$(2^2)^{3*2}=4096$$ and $$4096(mod7)=1$$ and $1\neq4(mod7)$ a contradiction.


1

Assume $p\ne q$. Note that every integer $Z\equiv(p+q)/2\pmod{pq}$ is a solution: writing $Z=(p+q)/2+kpq$, we can set $X=2kp+1$ and $Y=2kq+1$. (This sufficient condition turns out to be necessary as well.) And every residue class contains infinitely many non-primes (in fact, most elements are non-primes). Indeed, for any integer $n$ not divisible by $p$ or ...


1

You get trivial counterexamples by taking $X=Y=1$ so that $Z=(p+q)/2$, which is non-prime for lots of $p$'s and $q$'s, but let's look beyond that. It's clear that $X$ and $Y$ must be odd, so let's write $X=2m+1$ and $Y=2n+1$ with integers $m$ and $n$. The equations now are $$2Z=p+(2m+1)q=p+q+2mq$$ and $$2Z=q+(2n+1)p=p+q+2np$$ from which follows that ...


1

$$ Z \equiv p/2 \pmod q,$$ $$ Z \equiv q/2 \pmod p,$$ combine with Chinese Remainder Theorem. If you dislike $Z,$ keep adding $pq$ until you get something you like. If this makes you uncomfortable, rewrite as $$ Z \equiv (p+q)/2 \pmod q,$$ $$ Z \equiv (p+q)/2 \pmod p.$$ In any case, end with $X = (2Z-p) /q $ and $Y = (2Z-q) /p. $ Now that I think about ...


1

Yes, there are infinitely many solutions with $Z$ non-prime. One infinite family is given by considering any odd primes $p$ and $q$ such that $$p\equiv (+1)\pmod 6 \\ q\equiv (-1)\pmod 6$$ Then, $p+q\equiv 0\pmod 6$ and setting $X=Y=1$ and $Z=(p+q)/2$ yields a solution with non-prime $Z$. If you prefer less trivial solutions (e.g. with $X$ distinct from ...


0

Write your number as $2^a\times3^b\times5^c\times7^d\times11^e...$ Note that you store the previous largest divisor in $C$. Divisibility by $C$ would have no affect if you keep eliminating these lower primes. Once all lower divisors are eliminated you would have, say, $p^{\alpha}$. Next dividing by it would store it in $C$. Then you successively reduce ...


3

$2^5+3^5$ is divisible by $11$. So is $5^5+7^5$.


0

There are $\sim\frac{x}{\varphi(a)\log x}$ primes of the form $ak+b$ below x, a consequence of the prime number theorem in arithmetic progressions (as Greg mentioned).


1

Note that if $\vartheta$ is the Chebyshev function, we have the relationship \begin{align*} e^{\vartheta(x)} &= \operatorname{exp} \left(\sum_{p \le x} \log p\right) \\ &= \prod_{p \le x} p \end{align*} So asymptotic bounds for the Chebyshev function carry over to the desired product.


1

An elementary proof of this result is outlined in problem 36 on p. 108 of An Introduction to the Theory of Numbers by Niven, Zuckerman and Montgomery. That problem references the article by I. Niven and B. Powell "Primes in certain arithmetic progressions," Amer. Math. Monthly, 83 (1976), 467-469, as simplified by R.W. Johnson.


1

This is a rather simple statement that is written in a pretty unclear manner. What they are saying is that if p is a prime number and $p\vert ab \implies p\vert a$ or $p\vert b$ This can easily be proven with the following proposition: If a,b,c are integers with $c\vert ab$ and $gcd(a,c)=1 \implies c\vert b$ As people have said in the comments, the ...


1

Not so much an answer as adding another level to the same question. The Firoozbakht's conjecture (1982) is equal to: $$(p_{n+1})^{n} < (p_n)^{n+1}.$$ Then the natural log is: $$n \ln(p_{n+1}) < (n+1)\ln(p_n).$$ Now, $$\ln(p_n) \leq \ln(n) + \ln(\ln(n)) + 1\text{, for $n \geq 2$. (*)}$$ With $n = n+1$ we have: $$\ln(p_{n+1}) \leq \ln(n+1) + ...


0

I hope I got the programming right: I get $679$ pairs less than $10000$, of which the first few are $$ \eqalign{ [102,105], &[170,174], &[230,231], &[238,246], &[255,258], &[282,285], &[285,286],\cr [366,370], &[399,402], &[429,430], &[430,434], &[434,435], &[438,442], &[598,602],\cr [602,606], &[606,609], ...


0

Here's a list to get you started: $$[[230, 231], [255, 258], [285, 286], [429, 430], [434, 435], [609, 610], [645, 646], [741, 742], [805, 806], [902, 903], [969, 970], [986, 987], [1001, 1002], [1022, 1023], [1065, 1066], [1085, 1086], [1105, 1106], [1130, 1131], [1221, 1222], [1245, 1246], [1265, 1266], [1309, 1310], [1310, 1311], [1334, 1335], [1406, ...


2

Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 3 \pmod 4} $$ Lemma: $$ (-p|q) = (q|p). $$ Lemma: If $$ a^2 + p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$ Let $$ F_1 = 4 + p, $$ $$ F_2 = 4 F_1^2 + p, $$ $$ F_3 = 4 F_1^2 F_2^2 + p, $$ $$ F_4 = 4 F_1^2 F_2^2 F_3^2 + p, $$ $$ F_5 = 4 F_1^2 F_2^2 F_3^2 F_4^2 + p, $$ and so on. These ...


1

See http://arxiv.org/pdf/1305.3062.pdf for a detailed description of how the verification was obtained. It's pretty heavy though, as can be expected because naive verification would take far too long.


2

By quadratic reciprocity, $(p/q) = (-1)^{(p-1)/2}(-1)^{(q-1)/2}(q/p)$. Let $\chi$ be the Dirichlet character of conductor $4p$ given by $n \mapsto (-1)^{(n-1)/2}(n/p)$. Then the function $q \mapsto (q/p)$ is nothing but $q \mapsto (-1)^{(p-1)/2}\chi(q)$, almost a Dirichlet character (it is a Dirichlet character if $p \equiv 1 \mod 4$ and minus a Dirichlet ...


6

This concatenation is A007908 in the OEIS, where you can see that Charles Nicol and John Selfridge ask the same question in R. K. Guy, Unsolved Problems in Number Theory, A3. There are no primes in the first 5000 terms of the sequence, but heuristics suggest that there are infinitely many. In particular, there 'should' be about $$\frac{\log\log n-\log\log ...


0

You can verify or disprove the "if" part of your claim easily with a computer because the only quadratic imaginary fields with class number $4$ are given by $\mathbb{Q}(\sqrt{-d})$ where $d$ is one in the list 14,17,21,30,33,34,39,42,46,55, 57,70,73,78,82,85,93,97,102,130, 133,142,155,177,190,193,195,203,219,253, 259,291,323,355,435,483,555,595,627,667, ...


0

Write down the last digits of the powers of $7$ ($7^n$ modulo $10$): $$1, 7, 9, 3, 1...$$ They'll repeat after that point (why?). Since they'll repeat, you just need to figure out $11^{22^{33}}$ modulo $4$ (why modulo $4$?) and your answer is that element of the above list. The problem is recursive. To work out $11$ modulo $4$, you use the same process as ...


0

As $$7^4\equiv1\pmod{10}$$ $$7^{11^{22^{33}}}\equiv7^{11^{22^{33}}\pmod4}\pmod{10}$$ Now $\displaystyle11\equiv-1\pmod4\implies11^{(22^{33})}\equiv(-1)^{(22^{33})}\equiv1\pmod4$ as $22^{33}$ is even


2

For $n!$ look for the largest prime less than or equal to $n$. For example, for $82!$, I'd likely start at 82 and work down until I found a prime which would be 79. Consider a small $n$ like 5 for a moment. $5!=120$ where I'd claim that 5 is the greatest prime divisor of 120 as $120=5*4*3*2*1$ and thus the greatest prime will just be the largest prime in ...


1

Hint: Since $82! = 1\cdot 2\cdot 3\cdots 81$, every prime number that divides $81$ must divide one of the numbers $1,2,3,4\dots 81$.


0

Do you know the difference of squares formula? $$a^2-b^2=(a+b)(a-b)$$ Using this, your equation can be rewritten as: $$n=(1-0)(1+0)(2-1)(2+1)(3-2)(3+2)\dots (100-99)(100+99)$$ $$n=(1)(1)(1)(3)(1)(5)\dots (1)(199)$$ $$n=(3)(5)(7)\dots (199)$$ We can see that the largest prime that divides $n$ is $199$. All other factors of $n$ that are greater than $199$ are ...


0

Use "difference of squares": $(a^2-b^2)=(a+b)(a-b)$. From there you should be able to find the greatest prime factor pretty quickly.


0

Hint. $$n=(1-0)(1+0)(2-1)(2+1)(3-2)(3+2)\cdots(100-99)(100+99)\ .$$


3

The characteristic equation for the recurrence relations $u_{n+3} - 2u_{n+1} - u_n = 0$ is given by $$\lambda^3 - 2\lambda - 1 = (\lambda-1)\left(\lambda-\frac{1+\sqrt{5}}{2}\right)\left(\lambda-\frac{1-\sqrt{5}}{2}\right)$$ Since the roots are all simple, the general solution for $u_n$ has the form $$u_n = \alpha (-1)^n + \beta ...


1

This is just a difference equation so you can just solve this using standard method and after substituting initial values in I'm sure $u_p$ will have expression of the form $p \times f(p)$ of some sort where $f(p)$ is an integer.



Top 50 recent answers are included