New answers tagged

8

The polynomial $ x^6 + x^5 + x^4 + 3x^3 + x^2 + x + 1 $ can be factored through the following manipulations: $$x^3 (x^3 + x^2 + 1) + x^4 + 2x^3 + x^2 + x + 1 = (x^3 + 1)(x^3 + x^2 + 1) + x^4 + x^3 + x = (x^3 + x + 1)(x^3 + x^2 + 1) $$ Now, plug in $ x = 10^2 $ to get a factorization of your number, which easily confirms that your number is composite.


1

You might find that "funny mirror pattern" is close to some "funny mirro pattern" squared. Indeed, for digits $a,b$, we have $(a0b0\ldots)^2=a^202ab0\ldots$, so to match this with $1010\ldots$ or more generally with $x0x0\ldots$, we ought to have $a=2b$. The simplest case of this is $a=2$, $b=1$. It turns out that $2010102^2=4040510050404$ is just ...


3

It seems that $\,A(6071)\,$ is prime but since this number has $\,22968\,$ digits the generation of a certificate proving its primality may take a very long time (some 'records' with Primo using ECPP shown are here ). The digits of $A(6071)$ are here for those wanting to test (or infirm this conjecture) : (it is a strong pseudo-prime and passed the ...


4

The question that I found on Problem Solving Strategies by Arthur Engel (page 123 at this link) is that- I start with a multidigit number $a_1$ and generate a sequence $a_1,a_2,a_3,...$ Here $a_{n+1}$ comes from $a_n$ by attaching a digit $≠9$.Then I cannot avoid the fact that $a_n$ is infinitely often a composite number. The proof is as ...


18

It is known that there is a positive number $\delta$ strictly less than 1 such that, if $n$ is large enough, then there's a prime between $n$ and $n+n^{\delta}$. [I think the state of the art has $\delta=.535$] If $n$ is large enough, then $n$ and $n+n^{\delta}$ start with the same however-many-digits-you-like. So that proves it's always possible, although ...


1

For example, if A = {a, b, c, d} and B = {a, c, e, f, g}, it might be (?) that the division (efg)/(bd) has zero reminder although that A is not a subset of B. But does this happen for any possible combinations of primes up to a given prime number N, and is there a bound for such an N? If $e,f,g,b,d$ are prime, then $bd$ will not divide $efg$. I ...


0

For $P_A$ to divide $P_B$, all factors of $P_A$ must be factors of $P_B$. So basically, for $P_A$ to divide $P_B$, each element in $A$ must be in $B$. Thus $A\subset B$.


33

We have the number $10^{20}+1$. Whenever we have something in this kind of form, we need to find an odd factor of the exponent. In this case $5 \mid 20$, so we can use $5$ as the factor. Now, we can say $10^{20}+1=(10^4)^5+1$. How does this help us? Well, if we say that $x=10^4$, we have the polynomial $x^5+1$. This polynomial has $-1$ as a zero, meaning ...


10

We do not have $2^{74,207,281} − 1$ prime numbers by now. Instead, the largest number about which we know that it is a prime is $p=2^{74,207,281} − 1$. The actual number of primes of to $p$ should be around $p/\ln p$, but we do not "know" all of these in the sense that each of them has been computed by someone. Rather, those record-breaking primes are found ...


4

There have been various attempts at approximating the Prime Counting Function $\pi(x)$ which gives the number of primes $\leq x$. A simple approximation is $$\pi(x)\sim \frac{x}{\ln x}$$ We can get an approximation of the long-run frequency of primes by looking at: $$\lim_{n \to \infty} \frac{\pi(n)}{n} \approx \lim_{n \to \infty} \frac{n}{n\ln(n)} = ...


1

This has nothing to do with $p$ being a prime. It is true for all positive odd integers. Putting $p=18n+2k+1$ (with $0\le k<9$) it is easy to see that $1+9p(p-1)/2\bmod 81$ depends only on $k$, so for $k=0,1,2,\dots,8$ we find it is $1,28,10,28,1,10,55,55,10$. We also find $2^{54}=1\bmod 81$. So here we apparently get a cycle three times as long, but if ...


2

Choose some random composite integer $n$ that is a multiple of some prime $p$, other than $-1, 0,$ or $1$. Let's pull together the set of multiples of $n$ and call it $\mathfrak{n}$ (I'm a demon, so I like to make things confusing by using the same letter for different things). Clearly this set is infinite, but it does not contain all integers: ...


2

1) Is there any serious problem or inconsistency inside of mathematics if we take 1 as a prime number (other than just re-writing the theorems/lemmas/conjectures/definitions in a different way)? No, no serious problem, only a bunch of minor but unnecessary inconveniences. 2) Should we or should we not take 1 as a prime number? We should not. ...


6

I thought about what happens in bases b other than b = 10. We cannot have the digit zero, or any digit that is a composite number (for example in hexadecimal: 4, 6, 8, 9, 10, 12, 14, 15). The possible digits are the number 1 and the primes p < b. No digit other than 1 can appear more than once, since xx = x * 11 in every base. The digit 1 can appear ...


1

I think this is the most natural way to define a prime number: An integer $n$ is prime if it has exactly two integer divisors, up to equivalence. If you don't like thinking about equivalence, we can also say: A positive integer $n$ is prime if it has exactly two positive integer divisors. This is analogous to many other concepts in mathematics: ...


0

I have answered an extremely similar question before. I will edit my old answer to better suit this question. I am so old I was taught that definition, that it's enough for a prime number to be divisible only by $1$ and itself. But my children and grandchildren were taught that a prime number must have exactly two distinct divisors among the positive ...


1

I decided to compare this theorem to another favorite theorem of mine, Fermat's little theorem (which some people just call "Fermat's theorem). On ProofWiki, I went to the pages for both theorems and clicked "what links here": https://proofwiki.org/wiki/Special:WhatLinksHere/Fundamental_Theorem_of_Arithmetic , ...


0

Using the last result I proved in your previous question, namely that for any odd prime $p$ and any natural number $b$ not divisible by $p$ we have: $$\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2bk}{p}}\right\rfloor\equiv (b-1)\frac{p^2-1}{8}+\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{bk}{p}}\right\rfloor\text{ mod } 2$$ We can then set $b=a$ an even ...


0

If for an odd prime $p$ and an arbitrary natural number $b$ not divisible by $p$ we write out: $$\mu_p(b)=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor{\frac{2bk}{p}}\right\rfloor$$ Then using Eisenstein's lemma in his geometric proof of quadratic reciprocity we have: $$b^{\frac{p-1}{2}}\equiv (-1)^{\mu_p(b)} \text{ mod } p$$ Which as a result gives us: ...


1

In particular the little theorem of Fermat and Wilson's theorem would be valid because $a^{1-1}\equiv 1\pmod 1$ and $(1-1)!\equiv -1\pmod 1$ (since $a\equiv 0\pmod 1$ for all integer $a$). On the other hand $\mathbb Z/(1\cdot \mathbb Z)=\mathbb Z$ is not a field so, according to the corresponding well known theorem, $1$ is not a prime.


3

One way to prove that there are infinitely many primes is to show that the Fermat numbers $F_n=2^{2^n}+1$ are relatively prime. (Note that the $F_n$ themselves are not always prime). This is because $$ F_m=F_0F_1\cdots F_{m-1}+2$$ so if $p$ divides both $F_n$ and $F_m$ (with $n<m$) then $p$ divides $2$, which is impossible because none of the Fermat ...


0

HINT: Say the given $4$ values of $n$ are $n_1,n_2,n_3$ and $n_4$. For $3$ of the given values, the condition $11|(xyzw+n)$ holds. Say $11|(xyzw+n_1)$ and $11|(xyzw+n_2)$. So we have that $11|(xyzw+n_1)-(xyzw+n_2) \Rightarrow 11|(n_1-n_2)$ Now put the $4$ values and check.


1

It does follow from the prime number theorem: $$ \pi(x)\sim\frac{x}{\log x} $$ Indeed $$ \pi(ax)\sim\frac{ax}{\log ax}, \quad \pi(bx)\sim\frac{bx}{\log bx} $$ imply $$ \frac{\pi(bx)}{\pi(ax)} \sim \frac{bx}{ax}\frac{\log ax}{\log bx} \sim \frac{b}{a} > 1 $$ This implies that for $x \ge x_0$, we have $\pi(bx) > \pi(ax)$. Since they are both integers, ...


25

Extending André's answer and Travis's comment: Firstly, a 0 digit is ruled out since by definition it cannot be the first digit, and in any other position we could delete everything that follows it to leave a multiple of 10. All of which are composite since 10 is. With 0 excluded, every digit must be prime (1, 2, 3, 5, 7) because we could delete everything ...


1

Ruling out $n=1$ and $3|n$ we have the following conjecture : For every natural number $n$, there is a prime with digitsum $n$. The conjecture is definitely true for $2\le n\le 200$ (I found proven primes with PARI/GP) and very probably true for $2\le n\le 1000$ (The numbers I found passed $10$ strong probable-prime-tests) Since there are infinite ...


71

To build on the earlier answers, there are exactly twenty such numbers, and they are: 1, 2, 3, 5, 7, 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 311, 317 As can be found by the following program, which is correct as per Farewell's argument that seven digit and longer numbers cannot have the given property: import gmpy def test(n): if (not ...


109

It is clear that we cannot have digits $0,4,6,8,9$ in those prime numbers. There can be at most one $2$ because $22$ is composite,, at most one $3$ because $33$ is composite,at most one $5$ because $55$ is composite, at most one $7$ because $77$ is composite, at most two $1$`s because $111$ is composite, so such prime number can have at most $6$ digits so ...


41

There are only finitely many, indeed there are none with more than $3$ digits. Clearly our prime cannot have $0$ as a digit. If our prime has $4$ or more digits, and has $2$ or more not equal to $3$, we can by deleting one or two get a number greater than $3$ with digit sum divisible by $3$. And if there are two or more $3$'s we can produce $33$.


5

The fundamental theorem of arithmetic is important because it tells us something important and not immediately obvious about $\mathbb{Z}$ (the ring of the counting numbers together with those numbers multiplied by 0 or $-1$). Every nonzero number in $\mathbb{Z}$ can be uniquely factorized into primes without regard for order or multiplication by units. It ...


3

Asking whether for all $\varepsilon>0$ there are $m,n$ such that $\left|\frac{p^n}{q^m}-1\right|<\varepsilon$ is equivalent to asking whether for all $\varepsilon>0$ there are $m,n$ such that $\left|n\log(p) - m\log(q)\right|<\varepsilon$, or, if we prefer, such that $\left|\frac{\log(p)}{\log(q)} - \frac{m}{n}\right|<\frac{\varepsilon}{n}$ ...


0

The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n. Implemenation of Algorithm


2

Maybe it's interesting to see a proof of the convergence. From PNT we have that $$p_{n}\sim n\log\left(n\right) $$ as $n\rightarrow\infty $ so $$p_{p_{n}}\sim p_{n}\log\left(p_{n}\right)\sim n\log^{2}\left(n\right) $$ and we can observe that, using the integral test, that ...


2

Your link to the OEIS says that the series converges: "$\displaystyle\sum_{n\ge1} {1\over a(n)}$ converges. In fact, $\displaystyle\sum_{n>N} {1\over a(n)} < {1\over \ln(N)}$, by the integral test. --- Jonathan Sondow, Jul 11 2012."


5

For me, it's important because it tells you what numbers are made out of! It tells you that prime numbers are the "building blocks" of every number, and even better, this prime factorization is unique. So this tells you that a number just "is" a product of primes. Aside from being pretty cool (I think the proof is neat and easy to understand for how ...


2

If you allow non-monic polynomials the question is not very arithmetic in nature. Any class of integer functions closed under the operations $f(n) \to Af(n)+B$ with integer $A,B$, is guaranteed to have this property for any set that contains long arithmetic progressions (such as the primes, by the Green/Tao theorem as people have mentioned). This ...


1

The prime number theorem is equivalent to the asymptotic estimate $p_n \sim n\ln n$, which is a direct link between logarithms and primes (not just counting primes). So $p_n/n\sim \ln n$.


2

There are heuristic arguments that suggest that the probability that a random integer $n$ is prime is on the order of $\log n$. That's implicit in some of Euler's work. It's why the natural logarithm appears in the prime number theorem. See this question and some of the answers there: "Probability" of a large integer being prime


2

The prime number theorem can also be formulated with the integral logarithm, i.e., as $\pi(x)\sim li(x)$. So we do not necessarily have $x/\log(x)$ directly. Still we can say that the logarithm appears naturally in connection with asymptotic results on primes, e.g., $$ \sum_{p\le x}\frac{1}{p}=\log(\log(x))+c+O(1/x). $$ Perhaps more convincing for you than ...


0

One example that, $q$ being a prime, if $q | a$, $q^2$ does not necessarily divides $a$ is seen by taking $n=20$, $c=5$, and $a=10$. We can write $a^2 = nc$, then $n | a^2$. Note that $n$ has a square factor $2$ [$n=2^2(5)$], and by Euclid's Lemma $2 | a$. However, $2^2$ isn't a factor of $a$, so $n$ does not divide $a$.


15

This follows by the Green-Tao theorem: there exist arbitrarily long arithmetic sequences of primes. If $$ak+b,a(k+1)+b,\ldots,a(k+m^2)+b$$ are prime, we can take $P(n)=a(k+n^2)+b$, being prime for $n=0,\ldots,m$. Note that the same works if we require $\deg P=1$.


22

Yes. In fact, you don't even need the quadratic term: there are degree-$1$ polynomials giving arbitrarily long sequences of primes by the Green-Tao theorem. (Of course, you could also let $P$ be a constant prime).


1

The square roots of $-1 \pmod 5$ are $2,3 \pmod 5$ but $154 \equiv 4 \pmod 5.$ The square roots of $-1 \pmod {13}$ are $5,8 \pmod {13}$ but $154 \equiv 11 \pmod {13}.$ The square roots of $-1 \pmod {17}$ are $4,13 \pmod {17}$ but $154 \equiv 1 \pmod {17}.$ The square roots of $-1 \pmod {29}$ are $12,17 \pmod {29}$ but $154 \equiv 9 \pmod {29}.$ The ...


3

what i have observed from The concept you're looking for is called an Emirp: en.wikipedia.org/wiki/Emirp – Jasper 4 mins ago comment is as follows: NOTE: this is purely on the basis of the observation of the number given in the given list let there be such a number which is 'reversible prime'. Let $j$ be the sum of all the digits in that number from ...


1

My best guess would be that they just want you to do trial division by primes $p = 5,13,17,\ldots$ up to $36$ (there are much fewer primes to try with the $1$ mod $4$ restriction). For instance, to test whether $13$ divides $36^2+1$ you can compute $$ 36^2 + 1 \equiv (-3)^2 + 1 = 10 \not\equiv 0 \pmod{13}.$$ For $154^2+1$ you might in the worst case have ...


6

Yes, it is true, for odd $p$. The point is that a generator $g$ has order $p-1$, which is even. Yet, if $g= a^2$, then $g^{(p-1)/2} = a^{p-1} = 1$, a contradiction to $p-1$ being the order of $g$.


0

For your example you have $p=3, q=1, n = pq = 33$, so $\phi(n) = (p-1)(q-1) = 20$. Then $e = 7$ was chosen, which is indeed coprime with $n$. Then compute the greatest common divisor as done in this answer, and the link therein. So write $$ \begin{array}{rrr} 20 & 1 & 0\\ 7 & 0 & 1\\ 6 & 1 & -2\\ 1 & -1 & 3 ...


0

On The Euler (Totient) Function Multiplicity Define theTotient function as Eu(.). To prove Eu(N∙M) = Eu(N)∙Eu(M). The set 1:N∙M is partitioned into set of columns. Each column is a sum of a base column: C0 = [ 0, M, .. (N-1)M]’; and an offset - k; k: 1,2,..M; A column Ck is: Ck= C0 + k. An element of a column Ck is the ...


3

Here's an outline of the proof: Show that there are $14$ primes under $\sqrt{2015}$. Let $R$ be a set of $14$ composite coprime numbers under $2015$. It is well-known that any composite number has a prime factor under its square root, so in this case, each of these composite numbers has one of the prime factors under $\sqrt {2015}$. Now, using that ...


4

You can, in fact, do it with $b=1$, noting that this amounts to looking for a non-square integer of the form $$d={(ap-1)(ap+1)\over q^2}$$ To find such a $d$, note that $\gcd(p,q)=1$ implies there is a number $a_0$ such that $a_0p\equiv1$ mod $q^2$. If we now take $a$ of the form $a_0+kq^2$, we see that $ap+1=(a_0p+1)+kpq^2$, which means, by Dirichlet's ...



Top 50 recent answers are included