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