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
119 views

Finding the lowest common value in repeating sequences

Assume I have N sequences of ones and zeros. Each sequence repeats every p terms. I want to find the minimum position where all ...
4
votes
1answer
77 views

Number of times $g(p_1)$ occurs in $\sum_{d\mid n}g(d)$

$$ g(n)=\begin{cases} 1 & \text{if }n=1 \\[10pt] \sum_{d\mid n,\ d\ne n} g(d) & \text{else} \end{cases} $$ How can I calculate $g(n)$ efficiently? I was trying to collect all the $g(p)$ ...
6
votes
1answer
240 views

A Conjecture about Maximal Prime Gaps

As it is well known that prime number is $2,3,5\cdots \cdots$, thus all these prime number are denoted by$p_{1},p_{2},\cdots \cdots ,p_{n}\cdots \cdots$. The prime maximal gap $\max_{p_{n+1}\leqslant ...
35
votes
2answers
589 views

Is $n(n+1)$ ever a factorial?

Brocard's problem asks if $(n-1)(n+1)$ is ever a factorial. My question is similar: is $n(n+1)$ ever a factorial? This can be seen as the special case $k=2$ of the question: for $2\le k\le n-2,$ when ...
0
votes
2answers
281 views

Solutions to Trigonometric Problem Class

Is there a way to prove that the general solution of: $\sin^2 \pi x + \sin^2 \frac {ab\pi}{x} = 0$ is: $x = \pm 1,\pm a, \pm b, \pm ab$ and more specifically to derive the proof analytically, ...
2
votes
0answers
66 views

Can someone explain Goodstein theorem

I am a Computer science student.Can someone explain Goodsteins theorem and Application in computer science.
8
votes
0answers
111 views

Asymptotics of the lower approximation of a pair of natural numbers by a coprime pair

When we are working, for instance, in combinatorics or graph theory, sometimes we can have the following situation. For each number $m$ from an infinite set $\mathbb M\subset\mathbb N$ we can ...
1
vote
0answers
62 views

number of ways of expressing a number as sum of 5 squares modulo 10

Look at the function $r_5(n)$, which is defined by the number of ordered integers $(a,b,c,d,e)$ which satisfy $a^2+b^2+c^2+d^2+e^2= n$. Now, I have conjectured that the unit's digit of $r_5(n)$ is 2 ...
2
votes
0answers
64 views

theta function help

i need some help with this question Let $ \theta(z,t)= \sum \limits_{m,n\in\mathbb{z}}e^{-\pi Q_z(m,n)t} $ where $ Q_z(m,n)=y^{-1}|mz+n|^2. $ and i need to show $ \theta(z,t) = t^{-1} ...
2
votes
1answer
84 views

solving an equation about the number of divisors

Find all natural numbers $n$ such that $n=d(n)+1$ ($d(n)$ is the number of positive divisors of $n$) Any ideas on how to solve this ???
1
vote
0answers
80 views

Deriving this recursive expression for Riemann Prime Counting Function?

Why does this work? $f(n,k,1)=0$ $f(n,k,j)= \frac{1}{k} - f(\lfloor\frac{n}{j}\rfloor, k+1, \lfloor\frac{n}{j}\rfloor) + f(n,k,j-1)$ Here, f(n,1,n) computes the Riemann Prime Counting Function. ...
1
vote
1answer
246 views

How to find number of squares in a chess board

Problem : An $ n\times n$ chess board is a square of side $n$ units which has been sub-divided into $n^2$ unit squares by equally spaced straight lines parallel to the sides. Find the total number ...
7
votes
1answer
128 views

Find $a,b,c$ such that the equation $ax^2+a=by^2+b=cz^2+c$ has infinitely many integer solutions

Do there exist $3$ positive integers $a,b,c~(a<b<c),$ such that the equation $$ax^2+a=by^2+b=cz^2+c$$ has infinitely many integer solutions $x,y,z$ ?
5
votes
0answers
81 views

Constructing pairs of units $(x,y)$ which solve $x^2 + y^2 \equiv -1 \pmod{N}$

A classic result on the way to the Lagrange Four Squares theorem — for instance proven by Theorem 87 of Hardy & Wright, as noted by this remark on the Four Squares theorem — is that ...
3
votes
3answers
299 views

Finding the sum of two numbers knowing only the primes

Pretend $N_1$ is the prime factorization of 30 and $N_2$ is the prime factorization of 8. Is there a way, using only $N_1$ and $N_2$, to get the prime factorization of the sum, 38? It is easy to do ...
0
votes
2answers
632 views

Theory of Numbers Properties of GCD (Greatest Common Divisor) [duplicate]

I am a student in Undergraduate Mathematics, and I'm struggling to number theory ... I have this problem gcd, and do not know how to do it, and still do not study, congruences, Diophantine equations ...
6
votes
2answers
237 views

Ratio of sum of Euler's totient to $n$: $\lim_{n \to \infty} {\log \left( \sum_{k=2}^n \varphi(k) \right) \over \log(n)}$

This is more a casual/recreational question... It seems to me, that the limit as given in the subject line $$\lim_{n \to \infty} {\log \left( \sum_{k=2}^n \varphi(k) \right) \over \log(n)} = \log_n ...
2
votes
1answer
148 views

Mill's formula, $\theta^{3^n}$ is a prime for a certain $\theta$ and all natural $n$?

I just watched this video done by numberphile, and the video claimed that there exist certain numbers $\theta$ such that the floor function of $\theta^{3^n}$ is a prime for all natural $n$ . $\theta$ ...
2
votes
2answers
120 views

Generating function of a counting function.

Let $m$ be odd. Let $\eta(m)$ count the number of ways we can express $m$ as a product of exactly two odd numbers, counting order. What is $$\sum_{m\text{ odd }}\eta(m)x^m\text{ ? }$$ So, as an ...
6
votes
1answer
142 views

Relations between irreducibility on $\mathbb{Q}[x]$, and on $\mathbb{Q}_p[x]$ ($p$-adic numbers)

I'm reading "$p-$adic numbers: An introduction" by Fernando Q.Gouvêa, and I'm currently on page 79 of the book. Problem 121. Show that the equation $(X^2 - 2)(X^2 - 17)(X^2 - 34) = 0$ has a root ...
4
votes
1answer
119 views

Ring of integers of a degree $5$ extension

Consider the polynomial $P(X) = X^5 - X + 1 \in \mathbb{Q}[X]$, and let $x \in \mathbb{C}$ be a root of $P(X)$. Let $K = \mathbb{Q}(x)$. How can you prove that the ring of integers $\mathcal{O}_K$ is ...
0
votes
1answer
108 views

Is sum and product of $k$ natural numbers always different from that of some other $k$ natural numbers?

Suppose $k$ is say $3$. Let $A,B$ be a sets of $3$ natural numbers. $A$ not equal to $B$. Can sum and product of the elements in $A$ be same as that of $B$. If the numbers are primes then the ...
1
vote
1answer
1k views

Applying Extended Euclidean Algorithm for Galois Field to Find Multiplicative Inverse

I was trying to apply the Extended Euclidean Algorithm for Galois Field. Among the many resources available, I found the methodology outlined in this document easy to grasp. The above works fine when ...
1
vote
1answer
414 views

Find the largest divisor of an integer $b$.

I want to find out an efficient method to calculate the largest divisor of a very big integer $b$ which can be up to $\large 2^{1000}$. That is, I want to find out an integer $a < b$, such that ...
8
votes
2answers
800 views

How prove this $\sum_{k=1}^{2^{n-1}}\sigma{(2^n-2k+1)}\sigma{(2k-1)}=8^{n-1}$

Given the positive integer numbers $n$,prove that $$\sum_{k=1}^{2^{n-1}}\sigma{(2^n-2k+1)}\sigma{(2k-1)}=8^{n-1}$$ where $\sigma(n)$ is defined as $$\sigma{(N)}=\sum_{d|N}d$$ This problem I think is ...
0
votes
3answers
698 views

numbers between two real numbers

From my intuition, I believe that between two real different numbers ($a<b$), there are infinity many: (1) rational numbers, (2) irrational numbers, (3) algebraic numbers and (4) ...
1
vote
2answers
188 views

Does this inequality hold true, in general?

Let $$N = \prod_{i=1}^{\omega(N)}{{p_i}^{\alpha_i}}$$ be the prime factorization of the positive integer $N$. Does the following inequality hold true in general? ...
1
vote
1answer
66 views

Calculus Proof / Number Theory

Let $a_j$ represent a real number such that. $$ \frac{\sum_{j=-1}^{n} (n-j)!a_{j+1}}{(n+1)!} = 0$$ Prove $$\sum_{j=0}^{n} a_jx^j =0$$ has at least one solution such that $x \in (0,1)$ I tried to set ...
4
votes
1answer
93 views

Prime with a given digit sum

Suppose $n>1$ is not divisible by 3. Is there a prime such that the sum of its decimal digits is equal to $n$? More generally, given a base $b\ge2$ and $n>1$ coprime to $b-1$, is there a prime ...
0
votes
1answer
77 views

To which extent distribution of Riemann non-trivial zeros follow a gauss process?

I am trying to clearer and preciser understand to which extent the distribution of the non-trivial zeros of the Riemann $\zeta$-function follow a Gauss process? Yet, what I figured out from ...
1
vote
2answers
166 views

How many positive integers $n$ satisfy $n = P(n) + S(n)$

Let $P(n)$ denote the product of digits of $n$ and let $S(n)$ denote the sum of digits of $n$. Then how many positive integers $n$ satisfy $$ n = P(n) + S(n) $$ I think I solved it, but I need ...
4
votes
1answer
295 views

IBM Research Ponder This (June Challenge)

This was the challenge in last month's 'IBM Reseach Ponder This'. I just cannot get my head around the solution posted. Can someone explain further? Challenge Find a rational number (a fraction of ...
1
vote
2answers
217 views

Natural, Dirichlet Density of a set of primes.

Let $M$ be a set of prime numbers of $\mathbb{Q}$ . The limit $$d(M)= \lim_{s\rightarrow 1^+} \frac{ \sum_{p \in M} p^{-s} }{ - \log(s-1)}$$ Where $p$ is a prime of $\mathbb{Q}$ is called Dirichlet ...
5
votes
1answer
174 views

Dirichlet vs. logarithmic density

The Dirichlet density of A relative to B is $$ \lim_{s\to 1^+}\frac{\sum\limits_{n\in A}n^{-s}}{\sum\limits_{n\in B}n^{-s}} $$ and the logarithmic density of A relative to B is $$ \delta(A) = ...
4
votes
1answer
60 views

Fix point of squaring numbers mod p

Take the set of integers $\{0, 1, .., p-1\}$, square each element, you get the (smaller) set of quadratic residues. Repeat until you get a fix point set. The size of this set is a function of $p$. ...
1
vote
1answer
70 views

Lattice reduction to find a solution to congruence equation

I am implementing an algorithm to solve ternary quadratic equations. I have come to a situation where I have a congruence equation $X^2-aZ^2 \equiv 0 \ (mod \ b)$ with a known solution $(x_0, y_0) = ...
2
votes
0answers
175 views

Riemann hypothesis equivalence statement, where is my error?

I need some feedback on the following: According to the page about the von Mangoldt function at the Mathworld page, the Riemann hypothesis is equivalent to the statement: $$\psi = x + ...
3
votes
1answer
70 views

Number of primitive roots modulo p; asymptotic behavior

I know that number of primitive roots modulo p is $\varphi(p-1)$, where $\varphi$ is Euler totient function. I'm actually interested in asymptotic behavior of $\frac{\varphi(p-1)}{p-1}$ (percentage of ...
1
vote
2answers
59 views

Least complete Solutions

I know what least residues are and I can solve them, but apparently, for an equation like this: $$x^2 + x + 1 \equiv 0 \mod 195,$$ you have to find the least complete solutions. I tried looking for ...
3
votes
1answer
122 views

A curious fact on partitions of 7 integer and related question.

Let's start writing $7$ partitions, marking them with $n\ A$, where $n$ is a number of terms in partition and $A$ is a set of terms in it. $$\underbrace {7}_{1\ \{7\}} = 7$$ $$\underbrace {6 + ...
13
votes
1answer
369 views

Is there any pythagorean triple (a,b,c) such that $a^2 \equiv 1 \bmod b^{2}$

... or equivalently, is there a $D$, such that $a^2 - Db^2 = 1$ All I managed to do is to use the Euclid's formula $a = m^2 - n^2,\ b = 2mn$ to test for all $m,n$ between 1 and 3000.
9
votes
6answers
849 views

Find five prime factors of $3^{140 }- 1$

I tried to simplify $3^{140}$ but I couldn't go past $81^{35}$, any help would be greatly appreciated.
2
votes
1answer
246 views

Questions about integral normal bases for subfields of cyclotomic fields

An element $\theta$ in a Galois extension $L$ of $\mathbb{Q}$ is said to give an integral normal basis if the ring of algebraic integers in $L$ is $\sum \mathbb{Z}\sigma(\theta)$ with $\sigma$ running ...
2
votes
1answer
358 views

“Binary” number wanted

I search a 100-digit number, containing only the digits 0 and 1 ("binary" number ) and being the product of two distinct 50-digit-primes. Again, I search a method more efficient than simply creating ...
0
votes
1answer
84 views

Discrepancy between terms of sum and sum

My question is why the following happens, and whether we can correct (2) below to account for an errant factor of 2. By a slight generalization* of the argument of this problem we have I think that ...
1
vote
1answer
68 views

Division between two numbers of the form $u + v\sqrt 2$

I need to do a division $a/b$, where $a$ and $b$ are numbers of the form $u + v\sqrt 2$, and $u$ and $v$ are integers (I'll write $a = u + v\sqrt 2$ and $b = u' + v'\sqrt 2$). What is an effective ...
28
votes
2answers
519 views

Find $a,b,c,d,e$ such that $\dfrac{s}a+1,\dfrac{s}b+1,\dfrac{s}c+1,\dfrac{s}d+1,\dfrac{s}e+1$ are all perfect squares $ (s=abcde)$

Are there five distinct positive integers $a,b,c,d,e$ such that $\dfrac{s}a+1,\dfrac{s}b+1,\dfrac{s}c+1,\dfrac{s}d+1,\dfrac{s}e+1$ are all perfect squares ? $ (s=abcde)$ If ...
0
votes
1answer
234 views

the number of distinct elements in product sets

A programming assignment asked to two disjoint 3-element sets such that the product set has size 5. $\big| \{x\,y : x \in \{a,b,c\}, \;y \in \{d,e,f\},\; x \neq y\}\big|=5$ If we have two ...
2
votes
1answer
53 views

Kronecker-Weber does not apply

Let $K=\mathbb{Q}(\sqrt{D})\neq \mathbb{Q}$. Show that $K$ has an abelian extension that is not contained in $K(\theta)$ for any root of unity $\theta$. Hint: Find $u \in K $ such that $K(\sqrt{u})$ ...
5
votes
0answers
108 views

Relative density of images of diophantine polynomials

My current research project involves sampling a sequence along non-constant polynomials with non-negative integer coefficients defined over the natural numbers, and I'd like to be able to say when two ...