# Tag Info

8

A prime number $p$ divides $10^k-1$ if and only if $10^k \equiv 1 \bmod p$. But if $p \nmid 10$ then $10^{p-1} \equiv 1 \bmod p$ by Fermat's little theorem. Therefore $p$ divides $10^{p-1}-1$ for all prime numbers $p \not\in \{ 2,5 \}$.

8

With $(A,B) = (ga,gb), \gcd(a,b)=1$ then $$\sum_{A,B, \gcd(A,B) \le G} \frac{\gcd(A,B)^s}{\mathop{\rm lcm}(A,B)^s} = \sum_{g\le G} \sum_{a,b, \gcd(a,b)=1}\frac{\gcd(ag,bg)^s}{\mathop{\rm lcm}(ag,bg)^s}$$ $$= \sum_{g\le G} \sum_{a,b, \gcd(a,b)=1}\frac{g^s}{(abg)^s} = G \sum_{a,b, \gcd(a,b)=1}\frac{1}{(ab)^s}$$ $$= G \sum_d \mu(d)\sum_{u,v}\frac{1}{(d^2uv)^... 6 For high school level, showing non-primality is fair game, provided simple divisibility criteria can resolve it. Showing primality for a number such as the one you posted is definitely not fair game. One guideline would be: If the teacher can't show it easily, then it's not appropriate for students. 6 If x=0 or y=0 then x^6+y^6 is x^6 or y^6 which cannot be a prime. If x\ne 0\ne y and x^6+y^6 is prime then$$x^6+y^6=(x^2+y^2)(x^4-x^2y^2+y^4)=(x^2+y^2)(\,(x^2-y^2)^2+x^2y^2 )$$and the factor x^2+y^2\ge 2, so the factor (x^2-y^2)^2+x^2y^2 must be 1, which is not possible unless |x|=|y|=1 because$$(x^2-y^2)^2+x^2y^2\ge x^2y^2.$$So |... 6 So you know that x^6 + y^6 = (x^2 + y^2)(x^4 - x^2y^2 + y^4), and both are not factorizable over \mathbb Q. If a, b, c \in \mathbb Z and a = bc, then if a is prime, either b = 1 or c = 1. You already know that x^2 + y^2 = 1 if and only if (x, y) \in \{(0, \pm 1), (\pm 1, 0)\}. Let us briefly look at the other term. Actually, x^4 - x^2y^... 6 We prove that the second and the third claims are true. The second claim is true. If a=d\alpha, b=d\beta and (a,b)=d, we have \mathrm{lcm}(a,b) / b = \alpha = a / d. We may rewrite the sequence a_n using above.$$ a_1=1, a_n=\frac{\lfloor(n+1)\sqrt 3\rfloor}{\left(\lfloor(n+1)\sqrt 3\rfloor, (a_{n-1}+1)\cdots (a_1+1) 3 \right)}, \ \ n\geq ...

6

Yes: it's true that every prime $p \neq 2$ or $5$ divides some number of the form $10^k-1$. There is a simple way to prove this fact. Look at the remainders of $10^k-1$ when divided by $p$. Clearly there are only finitely many remainders, namely $0,1,2, \dots, p-1$. Since the numbers of the form $10^k-1$ are infinitely many, there are two of them which ...

5

If $f(n)=n$ then $p_1^{a_1} \cdot ... \cdot p_k^{a_k}=p_1^2+...+p_k^2$. From this it follows that $p_1|p_2^2+...+p_k^2$ and that $p_k|p_1^2+...+p_{k-1}^2$, that is, it is true that $p_2^2+...+p_k^2=ap_1$ and $p_1^2+...+p_{k-1}^2=bp_k$ for naturals $a,b$. If those two equalities are subtracted then it is obtained $p_1^2-p_k^2=bp_k-ap_1$, which is equivalent ...

4

By the way, here is an "all-you-can-eat" approach to generate counterexamples. Find a series of prime $7 \leq p_1 < \cdots < p_l$, and let $N = p_1^{e_1} \cdots p_l^{e_l}$. $10$ is relatively prime to $N$, so there is a number $m$ such that $3m \equiv 10 \pmod N$. Find a prime $x$ such that $x \equiv m \pmod N$. This is always possible by Dirichlet's ...

4

I believe the question asks for the largest prime representable in JavaScript, instead of the largest prime less than $2^{53}$, which is trivial to calculate. From this perspective, I have to point out that the suggested method using Number.MAX_SAFE_INTEGER is not reliable in a strict sense. The information provided in the question regarding Number....

3

Here are some additional things related Lehmer's totient conjecture that is known. Definition: If $n$ is composite then $\phi(n)<n−1$, hence there is at least one divisor $d$ of $n−1$ which does not divide $\phi(n)$. We call $d$ as the totient divisor of $n$. Trivially, if $n$ is prime then it has no totient divisor and if $n−1$ is prime then $n$ has ...

2

If $\pi(x)$ is the number of primes not greater than $x$, then $\pi(x)$ is continuous from the right and the Riemann-Stieltjes integral over $[2, 2 + \epsilon]$ will tend to zero. The first equation should be $$\sum_{p \leq x} \frac 1 {\sqrt p} = \frac 1 {\sqrt 2} + \int_2^x \frac {d \pi(t)} {\sqrt t} = \frac {\pi(x)} {\sqrt x} + \frac 1 2 \int_2^x \frac {\... 2 If f, g \ge 0, then yes it does (by limit comparison test). Otherwise, not necessarily. For example, consider$$ f(n) = \frac{(-1)^n}{\sqrt{n}}, \ g(n) = \frac{(-1)^n}{\sqrt{n}} + \frac{1}{n} $$Then f(n) \sim g(n) but \sum_{n =1}^{\infty} f(n) converges while \sum_{n =1}^ {\infty} g(n) diverges. 2 m=2131 seems to be a hard case. n=316 and n=496 show that no small factor is forced. On the other hand,$$2^n+2131$$is not prime for 1\le n\le 40\ 000 m=2\ 491 gives a prime for n=3\ 536 and 4\ 471 gives a prime for n=33\ 548 I can continue the search of hard cases in the case of interest. "Survivors" upto n=1\ 000 in the range [-10^5,... 2 There is no difference, each requirement implies the other. If \gcd(a,N)=1 then obviously N can't divide a because otherwise N would be a common divisor of a,N which is bigger than 1. Now suppose N does not divide a. Let d be a positive common divisor of a,N. Since N is prime we know d=N or d=1. But N does not divide a, hence ... 2 It's a somewhat startling result that any number, prime or not, that does not have 2 or 5 as a factor, will have a multiple that consists only of the digit 9. In elementary school we learned that if kn is our number that \frac 1n can be written as a repeating decimal with period of k digits. If we write out the k digits as a single integer K... 2 Consider what convergence usually means in \Bbb Z_p: That more and more digits (counting from the right) stop changing as the sequence goes on. In base p (for any prime p), the elements of the sequence n! gets more and more trailing zeroes, meaning any specific digit of \sum n! is eventually fixed and doesn't change any more, which again means that ... 1 Negate:   prime \, \color{#c00}{p\mid a} \iff p\mid a,p\iff \overbrace{p\mid (a,p)\iff \color{#c00}{(a,p)\neq 1}}^{\textstyle \hphantom{p\mid (a,p)} \ {\Longleftarrow\ \ (a,p)\mid p}} 1 You are correct that 2 and 5 are the only primes that are not factors of 10^k-1 for some natural number k. Your proof looks correct, but it can be shown more simply. Assuming as you have that for p not equal to 2 or 5, \frac{1}{p}=0.\overline{d_1d_2...d_r}, notice (or show — it’s not too hard) that$$\displaystyle{1\over p}=0.\overline{d_1d_2....

1

The number is a prime. This cannot be found out in reasonable time without a computer.

1

I am not sure, but, it seems that if the Diophantine equation in $4$ variables $$p^2-3p+2=\sum_{j=2}^{p-1}(4b_jc_j+2b_j+2c_j-j!)$$ does not have solutions with the conditions $p\geq 7$ and $b_j,c_j \in \mathbb N$ and $4b_jc_j+2b_j+2c_j-j!>0$ for $j=2,...,p-1$ then you should have a prime in the set $\{2!+p,...,(p-1)!+p\}$ This comment-answer can be used ...

1

Under the random model for the primes I find the probability there is a prime $n!+k$ is about $a_k= \prod_{n=1}^k (1-\frac{\ln (n!+k)}{n!+k})$ and the probability that for some $K\ge K_0$ there is no prime $n!+K$ is $$f(K_0)=\sum_{K\ge K_0} (1-a_K)\prod_{k=K_0}^{K-1} a_k$$ Then we need to estimate $a_k$ and $f(K_0)$, the random model says your conjecture ...

1

Just a long comment on the converse of Robert Israel's answer. The converse of this is not immediately obvious i.e even if $f(x) >0, g(x) > 0$ and $\sum_{x \le n} f(x) \sim \sum_{x \le n} g(x)$ we cannot automatically conclude that. A very good example of this was the proof of the prime number theorem. It was already known that $$\sum_{n \le x}\... 1 For every set of primes, the product of the primes minus one does the job. The residue modulo every prime p in the set is then p-1, hence the remainders are distinct. 1 What you ask follows from the Fundamental Theorem of Arithmetic, which states that every positive integer great than 1 has a unique prime factorization (up to arrangement of the prime factors). Hence, it follows that every integer n > 1 is either prime or a product of primes. 1 You can use the classic prime N-1 test. Set P = p_1p_2\dots p_k + 1 equal to the product of the primes + 1, then if you can find an integer a such that$$ a^{P-1}\equiv 1 \pmod{P}$$and$$ a^{\frac{P-1}{p_i}} \not\equiv 1 \pmod{P}\quad i=1,\dots,k  then $P$ is prime. If $a^{P-1} \not \equiv 1 \pmod{P}$ for any $a$ then $P$ is composite.

1

More generally, if $f(n=p_1^{a_1} \cdot...\cdot p_k^{a_k})=p_1^m+...+p_k^m$ and $f(n)=n$ then $p_1^{a_1} \cdot ... \cdot p_k^{a_k}=p_1^m+...+p_k^m$. From this it follows that $p_1|p_2^m+...+p_k^m$ and that $p_k|p_1^m+...+p_{k-1}^m$, that is, it is true that $p_2^m+...+p_k^m=ap_1$ and $p_1^m+...+p_{k-1}^m=bp_k$ for naturals $a,b$. If those two equalities ...

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