Tag Info

New answers tagged

1

As an example, the proportion of numbers that have $7$ as least prime factor is about $\frac 12 \cdot \frac 23 \cdot \frac 45 \cdot \frac 17=\frac 8{210}$ This will be exact for $n$ a multiple of $210$. More generally the fraction is $$\frac1p\prod_{\substack {q \lt p \\q \text{ prime}}}\frac {q-1}q$$ which will be exact if $n$ is divisible by $p$ ...


0

We write the number as $2^{1+a}3^{1+b}{5^{1+c}}n$ with $(n,30)=1$. The number of divisors of the number is $30=(2+a)(2+b)(2+c)\tau(n)$. Hence $\tau(n)=1\implies n=1$ ($\tau(n)$ is the number of divisors of $n$). So $2+a,2+b,2+c$ are $2,3,5$ in some order. There are $6$ solutions: $2\cdot3^2\cdot5^4=11250$ $2\cdot3^4\cdot5^2=4050$ ...


0

If $$ N= p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k}$$ then the number of its divisors is given by $(\alpha_1+1)\cdot\ldots\cdot(\alpha_k+1)$. So, in order that $30\mid N$ and $ d(N)=30$ we must have $\{2,3,5\}\subseteq\{p_1,\ldots,p_k\}$ and $(\alpha_1+1)\cdot\ldots\cdot(\alpha_k+1)=30.$ Now it is straightforward to check that the choice ...


1

Let $n \in \mathbf N$. Writing the primefactor decomposition as $$ n = \prod_p p^{\alpha_p(n)}, $$ we know that $n$ has $$ \tau(n) = \prod_p \bigl(\alpha_p(n)+ 1\bigr) $$ divisors. (For any $p$ in a divisor we can choose $p$ appearing form $0$ to $\alpha_p(n)$ times), we have as $30 \mid n$, that $\alpha_p(n) \ge 1$, for $p \in \{2,3,5\}$. On the other ...


1

This statement from your lecture notes If a number $n>1$ is not prime, then it has a prime factor. is true - but it's not a very good way to say what it's trying to say. Here's an expanded version. Every integer $n > 1$ has a prime factor. If $n$ happens to be prime then that prime factor is $n$ itself. If $n$ is not prime then it has a prime ...


1

Yes, all integers $n>1$ have prime factors. Composite numbers have prime factors less than themselves. Prime numbers have no prime factors less than themselves.


0

For any integer $a$ such that $(a,6)=1, a=6b\pm1$ where $b$ is any integer Now $(6b\pm1)^2=24b^2+24\cdot\dfrac{b(b\pm1)}2+1\equiv1\pmod{24}=1+24c$(say) $\implies(a^2-1)(a^2-19)=24c(24c-18)=24c\cdot6(4c-3)\equiv0\pmod{144}$ Now if $a^4-20a^2+19\equiv a^4-1\pmod5$ But $a^{5-1}\equiv1\pmod5$ by Fermat's Little Theorem if $(a,5)=1$ ...


4

I first took the smallest possible 5-digit number with all digits in strictly increasing order: 12345. Now, it is obviously divisible by 3 & 5 (divisibility tests); this rules out 3 or 5 being the answer. Then 12346 is obviously divisible by 2, hence 2 is also rules out (as 12346 also has digits in strictly increasing order). Now, notice that remainder ...


1

The function $\Omega(n)$ is, by definition, the number of prime factors of $n$, counted with multiplicity (that is, not necessarily distinct). For example, $\Omega(720) = \Omega(2^43^25) = 4+2+1 = 7$. The summatory function for $\Omega$ is indeed $F(x) = \sum_{n\le x} \Omega(n)$. For example, $F(8) = \Omega(1) + \Omega(2) + \cdots + \Omega(8) = 0 + 1 + 1 + ...


1

This constant appears in the conjectured asymptotic estimate on the number of twin primes below a given size, see here. It's also noteworthy that this constant wasn't just taken out of thin air, this can be actually derieved heuristically via Cramer's random model.


1

It appears to be called the "twin prime constant" because it comes up a lot in theorems and conjectures about twin primes. For example, from the relevant MathWorld page:


0

We see that $p^4=1(mod.5)$(little Fermat's theorem), every odd number $x$ is such that $x^2=1(mod. 3)$. So we have $(p^2-1)(p^2-19)=0(mod. 9)$. Finally, $p^4-20p^2+19=1+3=0(mod. 4)$. Then, $p^4-20p^2+19=0(mod. 180)$.


3

$180=5\cdot9\cdot4$ For any integer $p, p^4-20p^2+19\equiv p^4-2p^2+1\pmod9$ Now $p^4-2p^2+1=(p^2-1)^2$ For $(p,3)=1,p\equiv\pm1\pmod3\implies p^2\equiv1\pmod3\iff p^2-1\equiv0$ and for any integer $p, p^4-20p^2+19\equiv p^4-1\pmod{20}$ $\implies p^4\equiv1\pmod5$ by Fermat's Little Theorem for $(5,p)=1$ Now if $(p,2)=1$ $p\pm 1$ are even,$\implies ...


4

Let $p^4-20p^2+19 = (p^2-1)(p^2-19)$, and $180 = 6^2\cdot 5$. But $p\equiv \pm 1\pmod{6}$, so $p^2\equiv 1\pmod{6}$, thus $p^2-1 \equiv 1-1 = 0 \pmod{6}$ and $p^2-19 \equiv 1-19 = -18 \equiv 0 \pmod{6}$, therefore $6^2 \mid p^4-20p^2+19$. On the other hand $p\not \equiv 0\pmod{5}$, so $p^2\equiv \pm 1\pmod{5}$ and $p^4\equiv 1\pmod{5}$, thus $p^4-20p^2 + 19 ...


7

Square both sides and we get $a+b-2\sqrt{ab}=12-2\sqrt{35}$. Hence, $$\left\{\begin{array}{c} a+b=12\\ ab=35 \end{array}\right.$$ Solve for $a,b$, and we have $a=7,b=5$ or $a=5,b=7$. Of course only the first one is correct.


0

$$ x^4+4=\\ [(x^2)^2+4x^2+4]-4x^2\\ =(x^2+2)^2-(2x)^2\\ =(x^2+2x+2)(x^2-2x+2)\ldots $$


7

$$\Large 2^{11}-1=23\cdot 89$$ Take a look at the Wikipedia page on Mersenne primes. There are (currently) only $48$ known prime numbers $p$ such that $2^p-1$ is prime, after people have used computers to check millions.


3

A heuristic is that an integer $n$ is prime with "probability" one in $\ln n$, and so we can estimate the sum with its "expected" value: $$ \sum_{\substack{p \leq n \\ p \text{ prime}}} \frac{1}{p} \approx \sum_{k=2}^n \frac{1}{k \ln k} \approx \int_2^n \frac{\mathrm{d}x}{x \ln x} \approx \ln \ln n$$ In fact, the Meissel-Mertens constant is given by $$ M ...


2

By Sum of reciprocal prime numbers, $$\sum_{p \le n}{\frac1{p}} = C + \ln\ln n + O\left(\frac1{\ln n}\right)$$ Therefore $\ln \ln n$ fits the bill.


6

The easiest way to see that $$ -\log n+\sum_{k=1}^{n}\frac{1}{k} $$ is convergent is to write it as $$ -\log\left(1+\frac{1}{n}\right)+\sum_{k=1}^{n}\left(\frac{1}{k}-\log\left(1+\frac{1}{k}\right)\right)$$ and check that $\frac{1}{k}-\log\left(1+\frac{1}{k}\right)=O\left(\frac{1}{k^2}\right)$. In the same way, $$ ...


13

Yes there is a constant associated with the sum of the reciprocals of the primes. In particular, Mertens showed that $$\sum_{p \text{ prime } \le x} \frac1p - \log\log(x)$$ converges to a constant as $x\to \infty$. This is a result from 1874. I found the result in a paper: EULER’S CONSTANT: EULER’S WORK AND MODERN DEVELOPMENTS - By JEFFREY C. LAGARIAS ...


0

If you already know Fermat's little theorem, then: $$(a+b)^p\equiv (a+b)\equiv (a^p+b^p)\pmod{\! p}$$ and you're done. If not, then by Binomial theorem$$(a+b)^p-a^p-b^p=\binom{p}{1}a^{p-1}b+\binom{p}{2}a^{p-2}b^2+\cdots+\binom{p}{p-1}ab^{p-1},$$ which is divisible by $p$ (and you're done), because $p\mid \binom{p}{i}$ for any $1\le i\le p-1$. This is ...


3

Right, you're probably wanting to show that $p$ divides the binomial coefficient $$\binom{p}{i}=\frac{p!}{i!(p-i)!}=p\cdot\frac{(p-1)\cdots(p-i+1)}{i!}$$ and hence want to show that the fraction is actually an integer. Here's one approach: Let $m=(p-1)\cdots(p-i+1)$, and let $n=pm$. We know that $i!\mid n$ because binomial coefficients are integers, and ...


2

Note that $$\frac{p(p-1)(p-2)\cdots(p-i+1)}{i!}=\binom pi$$ that is, an integer. And it is multiple of $p$ since $p$ is not a factor of $i!$.


0

In general, let $d$ be a natural number and $f(d)$ the greatest common divisor of all numbers of the form $p^d-1$, where $p\geq d+2$ is a prime integer. Denote by $g(d)$ the product of all numbers of the form $q^k$, where $q$ is an odd (positive) prime and $k$ is the largest positive integer such that $q^{k-1}(q-1)$ divides $d$. We also define ...


3

You correctly observed that $8$ must divide the number. However, $16$ must also divide it, since one of $p- 1 $ or $p+1 $ is a multiple of $4$. Furthermore, $16$ is the largest power of $2$ that divides the number, since $p^2 +1$ is never a multiple of $4$. $3 $ divides our number since $p $ is not a multiple of $3 $ and thus one of $p+1 $ or $p-1$ is a ...


4

I would like to promote the idea of calculating with small examples, hoping to see a pattern. $$ \gcd( 7^4 -1, 11^4 - 1) = 240. $$ $$ \gcd( 7^4 -1, 11^4 - 1,13^4-1) = 240. $$ So, it seems to be $240.$ the others have given enough arguments to show this is the final answer. My point is that students ought to learn to try easy cases, smaller problems, ...


9

Hint : $p>5$ so $p$ is not divisible by $3$, hence either $p-1$ or $p+1$ is divisible by $3$. So $3$ divides $p^4-1$. So $3$ divides it and $8$ divides it. Added: Notice that $p-1$ and $p+1$ are consecutive multiples of $2$, so one them is divisible by $4$. As Batimovski suggested, you can use Fermat's little theorem to conclude that $p^{4} \equiv 1$ mod ...


-1

Look up Meissel's prime-counting function. One reference is here: https://en.wikipedia.org/wiki/Prime-counting_function


2

A good survey about this question is the article Wieferich Past and Future by Nicholas M. Katz. In section $1$ the consequences regarding FLT are discussed. However, since there is a proof of FLT the motivation for going further there has disappeared. However, other aspects related to elliptic curves, abelian varieties and semiabelian varieties are still of ...


2

For sure, there are infinitely many even integers that cannot be written as $p^2-q^2$ where $p,q$ are primes. You only have to look at integers of the form $4k+2$ (or $8k+4$), where $k\in\mathbb{Z}$. Also, there are infinitely many even integers that cannot be written as $p^3-q^3$. Just look at integers of the form $2r$, where $r$ is a positive prime such ...


1

I wrote some Perl modules that relate to this, so I thought I'd try them out. Use cpan ntheory Data::BitStream Data::BitStream::XS then: #!/usr/bin/env perl use warnings; use strict; use ntheory qw/:all/; use Data::BitStream; my($s1,$s2,$s3) = map { Data::BitStream->new } 1..3; my $k=2; for my $n (1 .. 1_000_000) { $s1->put_arice($k,$n); ...


1

Because $0 \leq r < k$, we have $2k > k + r$. Also, note that $$\frac{x}{k} = \frac{kl + r}{k} = l + {r\over k}$$ which is certainly greater than $(l-1)$. Therefore, $$k+(l-1)\phi(k) + r \le 2k+{x\over k} \phi(k).$$


1

This answers the originally posted form of the question. For the edited form, the inequality as rewritten below clearly holds because of $0\le r\lt k$. This is not true under the conditions stated. Solving $x=kl+r$ for $l$ and substituting into the inequality leads to $$r-\left(\frac rk+1\right)\phi(k)\le k$$ This does not hold e.g. for $k=2$, where with ...


3

With looking to the method advised in the Jeppe Stig Nielsen's comment we can complete the proof for the claim which there aren't such these polynomials. In this paper it's proved which for every $m$ we have: $$\liminf_{n\to \infty} p_{n+m} - p_{n} < \infty $$ and thus if the above polynomials $P(x)$ and $Q(x)$ exist then for some fixed $k$ and ...


4

The "it can also be shown" expression is wrong. It only contains terms with up to two different prime factors. Write it out for $k=3$ to see that it differs from the correct expression by a term $\zeta(s)(2\cdot3\cdot5)^{-s}$.


0

Every prime number $p$ can be writen as: $$p=4k\pm1$$ and $$\displaystyle\lim_{n\to\infty} \frac{|\{p\in\mathbb{P}: \exists n\in\mathbb{N}/ p=4n+1\}|}{|\{p\in\mathbb{P}: \exists n\in\mathbb{N}/ p=4n-1\}|}=1$$ where: $\mathbb{P}=\{n\in\mathbb{N}: n \mbox{ is prime }\}$ $|A|= card(A)$ It means, there are an equal number of primes of the ...


1

We share profession (and indeed right know I am programming using .NET as well) and in my case is the first time I hear about the possible problems of harmonics in computer programming. I think the harmonics would not be a problem at all as the rest of people said in the comments. But in other hand, you could have a point if the reason of using prime ...


7

No. WolframAlpha says that $u_4$ is not prime and is equal to $$1676083\times \\26955961001\times\\ 29608434354586376051669975373338765263536609888911641073166192\\ 42535637290590853367799328108998193136129252550026666912268005\\ 07277398580985624625950496168983999760414855301693388419156899841$$


1

The prime number theorem is proven by relating a certain sum over primes to a sum over the zeroes of the zeta function. In particular, this amounts to a relation of the form I call $(1)$ in this answer to another question. As you look at that equation, you should note that called $\zeta(s)$ exactly $\pi(x)$ is not a sensible comparison. In fact, the prime ...


2

Let $q$ be any positive integer, and for $n \ge 0$ set $$ U_{n} = \frac{q^{n} -1}{q-1}. $$ You want to prove that for $m, n \ge 0$ $$\tag{gcd's} \gcd(U_{n}, U_{m}) = U_{\gcd(n, m)}. $$ This follows from the elementary fact that $U_{n}$ divided by $U_{m}$, with $m > 0$, leaves as a remainder $U_{r}$, where $r$ is the remainder of the division of $n$ by ...


3

Nope they are not. $7$ is a common divisor!


1

You can certainly do this, and I can imagine situations where it might be useful. For instance, suppose you take the normal decimal valuation of each place (ones, tens, hundreds, etc.), but allow "digits" from $0$ through $A$. Then operations like addition and multiplication can be carried out with the usual algorithm, but with some flexibility about ...


-2

You won't be thrown in jail for defining a bad number system, but you can certainly earn the scorn of professional mathematicians and wannabes, which in the big picture of things is not such a terrible thing. In my opinion, it's better for a number to have more than one representation than it is for one representation to correspond to more than one number. ...


1

Consider the number $143$. This number is composite, not prime, because $$11 \times 13 = 143.$$ But $$\sqrt[3]{143} \approx 5.229 < 11 < 13,$$ so if you test only possible factors up to $\sqrt[3]{143}$ then you will not check whether $11$ or $13$ divide $143$, and you will not discover that $143$ is not prime. On the other hand, $$11 < ...


3

If n is a sum of 2 addends, one addend must be $\leq n/2$ If n is a sum of 3 addends, one addend must be $\leq n/3$ If n is a sum of 4 addends, one addend must be $\leq n/4$ etc... If n is a product of 2 factors, one factor must be $\leq \sqrt{n}$ If n is a product of 3 factors, one factor must be $\leq \sqrt[3]{n}$ If n is a product of 4 factors, one ...


3

Sure, you can define anything you care to. In fact many commonly used systems, like decimal numbers, have elements with multiple representations like $0.999\ldots=1.$ Another example would be fractions, where $1/3=2/6.$ See A066352 in the OEIS for an example of an early use (by S. S. Pillai) of this particular system, and see also the related sequence ...


0

It is possible. The usual decimal representation of the the reals numbers has two representations for any number with a finite number of decimal places. For example. $1=0.\overline 9$.


3

It is certainly allowed for a number to have multiple representations in a system of representations. In fact, the decimal system which we use all the time has this property. The well known fact that $$1=0.999...=0.\overline{9},$$ is an example of this. Whether there is any practical use to the system you mention I don't know, but it seems unlikely. In the ...



Top 50 recent answers are included