Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

1
vote
1answer
32 views

Is this a good generating function for Sum-of-divisors function?

I have an expression for the sum-of-divisors function defined as $$\sigma(n)=\sum_{d\mid n}d.$$ However I do not know how nontrivial or practical it actually is. Let us define ...
0
votes
0answers
10 views

A diophantine problem with big numbers!

Find all pairs of positive integers $(a, b)$ such that $a^2 b^2 +300 | a^2(300 b^2 -a)$ and $300 b^2 -a>0$. I've tried so many different ways, I only concluded that $a<300$.
1
vote
1answer
16 views

Recurrence relation between solutions of a quadratic Diophantine equation

I have the fundamental solution of the following Diophantine equation: $$\frac{x(x-1)}{y(y-1)}=\frac{m}{n} \hspace{5 mm}, \hspace{5 mm} m \le n$$ $$nx^2-my^2-nx+my=0$$ Is it possible to derive a ...
1
vote
1answer
17 views

Largest Number that cannot be expressed as 6nm +- n +- m

I'm looking to find out if there is a largest integer that cannot be written as $6nm \pm n \pm m$ for $n,m$ elements of the natural numbers. For example, there are no values of $n,$m for which $6nm ...
4
votes
2answers
264 views

Formula for prime counting function

I saw this formula on this paper page 2 $$\pi (n)=\sum_{j=2}^{n}\frac{\sin^{2}\left(\pi \frac{(j-1)!^{2}}{j}\right)}{\sin^{2}(\frac{\pi }{j})}$$ Where $\pi(n)$ is the prime counting function. Is ...
1
vote
4answers
54 views

Prove that $1^2 + 2^2 + … + (n-1)^2 < \frac {n^3} { 3} < 1^2 + 2^2 + … + n^2$

I'm having trouble on starting this induction problem. The question simply reads : prove the following using induction: $$1^{2} + 2^{2} + ...... + (n-1)^{2} < \frac{n^3}{3} < 1^{2} + 2^{2} + ...
5
votes
2answers
95 views
+50

Variation of the Josephus problem

Suppose we have a circle of $2n$ people, where the first $n$ people are good guys and the people $n+1$ to $2n$ are bad guys. Can we always choose an integer $q$, such that if we execute successively ...
4
votes
2answers
141 views

a certain simple continued fraction

Given the golden ratio: $$\phi=\frac{1+\sqrt{5}}{2}$$ and the following simple continued fraction: $$G(q,k)=\cfrac{1}{1-q+\cfrac{1}{1-{q^3}^k+\cfrac{1}{1-{q^5}^k+\cfrac{1}{1-{q^7}^k+\ddots}}}}$$ For ...
4
votes
0answers
37 views

$\tau$ and grouping of prime numbers

From Prime Number Theorem and this we can state $$\frac{p_n}{\bar{p}}\sim 2$$ or $$\lim_{n\to \infty} \frac{np_n}{(p_1 + \dots +p_n)} = 2$$ If we then look at the fluctuations in the graph of $$f(n) ...
-1
votes
1answer
38 views

$3x + 1$ problem: other repetitions [on hold]

The Collatz problem: Pick an integer $x > 0$ If $x$ even: $x = x / 2$, if $x$ odd: $x = 3x + 1$ repeat 2.) as long as you want This algorithm seems to always end up with the loop $4, 2, 1$ My ...
2
votes
0answers
44 views

“Race” of the primes modulo $1,3,7,9\ \pmod {10}$

The "race" starts with the prime $11$. The number of primes $1, 3, 7, 9 \pmod {10}$ is denoted after every occurring prime. Does the lead change infinitely often? And does every "runner" have ...
3
votes
1answer
61 views

Existence of a map $\phi \colon \mathbb N\cup \{0\} \rightarrow \mathbb N\cup \{0\}$ that holds the property $\phi (ab) = \phi(a)+ \phi(b)$

Does there exist a map $\phi \colon \mathbb N\cup \{0\} \rightarrow \mathbb N\cup \{0\}$ that holds the following property? $$\phi (ab) = \phi(a)+ \phi(b)$$ If they do what do they ...
2
votes
0answers
9 views

Wireless networks on two sequential office floors: Random partitions of a finite interval via a point process on a line

Construct a Poisson point process of density one on a line of length $L$. Allow each point in the process to "see" part of the line to their left, and part of the line the their right (such that the ...
-4
votes
0answers
51 views

Lepore primality test and factorization . What is the complexity?

I have found an algorithm which tests if a number NR is primes . What is the complexity? I show only NR = X * Y, where NR = 6G + 1, X = 6a + 1, Y = 6b + 1, G, a and b natural numbers. X and Y are ...
2
votes
2answers
58 views

Solving a quadratic Diophantine equation

I want to solve the following quadratic Diophantine equation: $$\frac{x(x-1)}{y(y-1)}=\frac{p}{q} \hspace{5 mm}, \hspace{5 mm}p\le q$$ For $p=1$ and $q=2$, it is easy to solve. Let $y=x+z$. Then ...
333
votes
27answers
34k views

Different methods to compute $\sum\limits_{k=1}^\infty \frac{1}{k^2}$

As I have heard people did not trust Euler when he first discovered the formula (solution of the Basel problem) $$\zeta(2)=\sum_{k=1}^\infty \frac{1}{k^2}=\frac{\pi^2}{6}.$$ However, Euler was Euler ...
2
votes
1answer
51 views

Prove that $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \pmod p$

I'm trying to prove the statement $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \mod p$ and I don't really know where to start. Obviously $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} = 2\sum_{t=1}^{(p-1)/2} ...
4
votes
2answers
88 views
+50

Pentagonal Numbers

I recently was passing some time on Project Euler, when I came across this question. It deals with finding Pentagonal Numbers $P_j$ and $P_k$ such that $P_j+P_k$ and $P_j-P_k$ are also pentagonal ...
3
votes
1answer
74 views

Which constellations of primes recur forever?

Having derived much joy and learning from the answers I have received to four previous questions, let me ask one more. Let a constellation of primes be a set of primes that stand in certain fixed ...
1
vote
1answer
189 views

Would this proof strategy work for proving the lonely runner conjecture?

The problem is the lonely runner conjecture. This conjecture states that if $k$ runners begin running down a circle of unit circumference with random speeds, it will always the case that all runners ...
3
votes
1answer
27 views

Prove $v,w\in Z_{p}\times Z_{p}$ is linearly independent when $p=2$ and dependent when $p=3$

I need to prove that $\{v=(6,9),w=(7,8)\}\in Z_{p}\times Z_{p}$ is linearly independent when $p=2$ and linearly dependent when $p=3$. The problem is my freshman algebra course did not cover rings and ...
3
votes
1answer
29 views

the least $m$ such that $a^m\equiv 1 \mod n $ for fixed $a,n$.

Is there any known method for calculating $\lambda_a(n)$ which returns the smallest integer $m$ such that $a^m\equiv 1 \pmod n$ where $\gcd(a,n)=1$ ? I searched but I found nothing, is there at ...
2
votes
1answer
30 views

Is there a finite initial generating set for ${\mathbb N}$ given these two operations?

This is inspired by a recent question. Suppose we have $x_j \in \mathbb{N}$, and then we are allowed to perform any sequence of the following two operations: 1) Multiply by $k$ for some fixed $k \in ...
0
votes
1answer
23 views

What should be the approach for finding the remainder

How can one approach this kind of question: Find the remainder when $\left((7!)^{6!}\right)^{17777}$ is divided by 17
6
votes
0answers
45 views

Riemann zeta function Euler product for primes equivalent to $3$ mod $4$

Question: can $$ \zeta_1(s) = \prod_{p \equiv 3 \pmod{4}} \frac{1}{1 - p^{-s}} $$ be evaluated or written in terms of standard functions? Details: We can write the Riemann zeta function as ...
15
votes
4answers
1k views

Probability that a natural number is a sum of two squares?

Some natural numbers can be expressed as a sum of two squares: $$2=1^2+1^2$$ $$25=3^2+4^2$$ $$50=7^2+1^2$$ If one chooses a random natural number, what would be the probability that that number is a ...
2
votes
4answers
3k views

How many numbers below $100$ can be expressed as a difference of two perfect squares in only one way?

How many numbers below $100$ can be expressed as a difference of two perfect squares in only one way? Please explain your approach. ADDED: I can determine whether a number could be represented ...
0
votes
1answer
18 views

$(w^2+x^2).(y^2+z^2)$ is always divisible by which of the max no. Where w;x;y;z are positive odd integers?

Q $(w^2+x^2).(y^2+z^2)$ is always divisible by which of the max no where w,x,y,z are positive odd integers? Options given: 20;8;4;2 My Approach: I Choose ($9^2$+$5^2$).($7^2$+$3^2$) to get ...
5
votes
1answer
54 views

Proving that and how $ \frac{1}{n}\sum\limits_{p\le n}\lfloor n/p \rfloor - \sum\limits_{p\le n} 1/p $ approaches $0$

Let $p$ denote a generic prime number. By Mertens' second theorem, the sequence $$\sum\limits_{\ p \le n} \frac1p - \log\log n$$ converges to the Meissel-Mertens constant $M\approx 0.2614972$. Now let ...
19
votes
2answers
167 views

For all $n$ there exists $x$ such that $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$

Let $\varphi$ be the Euler's function, i.e. $\varphi(n)$ stands for the number of integers $m \in \{1,\ldots,n\}$ such that $\text{gcd}(m,n)=1$. Let $n\ge 2$ be a positive integer. Show that there ...
-3
votes
1answer
350 views

Is this attempted proof of ABC conjecture correct [closed]

This mathematician claims that he has tackled ABC conjecture! He uses induction and simple inequalities to achieve the result. Is this some serious stuff or is there a basic flaw in the reasoning?
0
votes
2answers
20 views

Simulataneous equations

Suppose you have the following system of linear congruence 2x+5y is congruent to 1 (mod6) x+y is congruent to 5 (mod6) where x,y belong to the set of Integers How would you obtain a general ...
1
vote
1answer
22 views

Finding Maximum in a Set of Numbers [on hold]

If I have a set of $n$ numbers: $(a_1,..., a_n)$, then how can I find the two maximum numbers in the set? Suppose that all the numbers are positive integers.
0
votes
0answers
37 views

Find all integers $m,n$ for which $m^2+n^2$ is a square and $\sqrt{\frac{2m^2+2}{n^2+1}}$ is rational

This is a repost of my old question here. The question is as follows: Find all integers m and n, such that $m^2 + n^2$ is a square and $\sqrt{\frac{2(m^2+1)}{n^2+1}}$ is rational. I have made no ...
2
votes
1answer
47 views

Can different tetrations have the same value?

Suppose, we have two numbers $a\uparrow \uparrow b$ and $c\uparrow \uparrow d$. To avoid trivial cases, suppose $a,b,c,d>2$ and $(a,b)\ne (c,d)$. Is there a quartupel $(a,b,c,d)$ with ...
6
votes
2answers
85 views

Does the Riemann-Hypothesis imply the Twin-Prime-Conjecture?

The Riemann hypothesis (https://en.wikipedia.org/wiki/Riemann_hypothesis) is one of the most important conjectures in number theory. I read that the Riemann hypothesis implies the Goldbach Conjecture ...
3
votes
0answers
39 views

Is there anything known about the zeros of $\displaystyle \sum_{n=1}^{\infty} \left(\frac{1}{\rho_n^s} +\frac{1}{\overline{\rho_n}^s}\right)$?

Assuming the RH and $\rho_n =\frac12 + \gamma_n i$ being the n-th non-trivial zero of $\zeta(s)$, then numerical evidence suggests that: $$f(s) :=\displaystyle \sum_{n=1}^{\infty} ...
0
votes
1answer
58 views

Roots of $\Phi_{31}(x)$ as roots of unity.

Let $\Phi_{31}(x)$ be the $31$-cyclotomic polynomial. I want to show that $\Phi_{31}(x)$ is the product of six irreducible quintic factors in $\mathbb{F}_2$. I am running into difficulties ...
-2
votes
1answer
27 views
3
votes
0answers
35 views

Can the determinant of an integer matrix with $k$ given rows be the gcd of the determinants of the $k\times k$ minors of those rows?

I'm interested if the following is true: Let $n\geq k\geq1$ be integers, let $A\in\mathbb Z^{k\times n}$ and denote the $\binom nk$ $k\times k$ minors of $A$ by $A_1,\ldots,A_N$. Then the ...
1
vote
0answers
28 views

Are there other known continued fractions that show the digits of the golden ratio?

I found a few. {16; 5, 1, 1, 5, 22} {161; 1, 4, 11, 1, 1, 3, 6, 1, 13, 8, 1, 6, 1, 4, 1, 1, 2, 1, 1, 1, 1, 13, 2, 1, 3, 8, 1, 2, 19, 1, 54, 1, 19, 2, 1, 8, 3, 1, 2, 13, 1, 1, 1, 1, 2, 1, 1, 4, 1, 6, ...
-4
votes
1answer
47 views

Crude verification of Goldbach conjecture [on hold]

So the Goldbach conjecture says 'Every even integer greater than 2 can be written as sum of two primes'. Here is what I have roughly done to verify it, using probability. I don't say it is correct but ...
1
vote
1answer
22 views

Proving a simple modulo equality

I'm probably lacking some basic concept here but I'm trying to prove that $$ ((a \mod k) \cdot k + b) \mod k = (a \cdot k + b) \mod k$$ I get stuck at the passage where, applying distributive ...
0
votes
0answers
30 views

How can there be an infinite number of sequentially composite Fibonacci(p)?

I ran into this counting function a(n)>=a(k)+1 for the number of distinct prime factors of the n-th Fibonacci number, at OEIS. Thank you Robert Israel! Thank you for writing the proof there. I had ...
5
votes
1answer
86 views

Thue equation $ x^4 - 6 x^3 y - x^2 y^2 + 6 x y^3 - y^4=-1 $

I need help solving the Thue equation $ x^4 - 6 x^3 y - x^2 y^2 + 6 x y^3 - y^4=-1 $. It can be written as $ x(x-y)(x+y)(x-6y) = (y-1)(y+1)( y^2 +1) $. From this I found 8 solutions ...
129
votes
1answer
7k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
0
votes
2answers
43 views

Can absolute value functions be moved like this?

If I have an expression that looks like $|x-a_1| + |x-a_2| + |x-a_3| + ... + |x-a_n|$ Is it the same as doing $|nx - \sum_{i=1}^{n}a_i|$
-3
votes
3answers
56 views

Prove that: 1. $gcd(a,b)=lcm(a,b)$ iff $|a|=|b|$ 2. $k>0\implies lcm(ka,kb)=k lcm(a,bk)$ 3. $a\mid m, b\mid m$, then $lcm(a,b)\mid m$

Let $a,b$ any non-zero integers. Prove that: $gcd(a,b)=lcm(a,b)$ If and only if $|a|=|b|$. If $k>0$, then $lcm(ka,kb)=k lcm(a,bk)$ if $m$ is multiple of $a$ and $b$, then $lcm(a,b)$ divides $m$ ...
0
votes
1answer
29 views

Calculate the number of zeros in square of ((4404 with base 17)) . ..?

Q Calculate the number of zeros in square of (4404 with base 17)? My approach: @Edit is it right? (4404 at base 17)*(4404 at base 17)=(10G0GF0G at base 17) So, the number of zeros will be 3.
0
votes
1answer
28 views

Show that (c,a)=(c,b)

In my book I have the implication: If $gcd(a,b)=1$ and $c|(a+b)$, then $gcd(c,a)=gcd(c,b)=1$. It gives me a hint that begins by supposing that $gcd(a,c)=gcd(b,c)=d$. But in my opinion, I do not ...