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)

0
votes
0answers
17 views

Is the relationship between coprime integers and irreducible fractions biconditional?

Are coprime integers and irreducible fractions related biconditionally? That is, if two integers are coprime ($a$ and $b$ say) then the fractions $\frac{a}{b}$ and $\frac{b}{a}$ are both irreducible. ...
3
votes
1answer
20 views

Maximum length of a string that has no substring divisible by a prime number $p$ is $p-1$?

What is the maximum length of a string of nonzero digits that has no substring that is divisible by a given prime number? I want to find a string of length n which has no substring divisible by the ...
3
votes
1answer
93 views

multiples (of primes) coverage formula

I apologize in advance if my explanation is not clear. Please let me know if clarification is required and I will do my best to fix it! I am attempting to find an explicit formula (in terms of ...
1
vote
2answers
39 views

Getting characteristic polynomial from a small matrix

Sorry I don't know how to format matrices, but if I have this matrix $\pmatrix{1& 1& 0\\ 0& 0& 1\\ 1 &0& 1\\}$ How is the characteristic polynomial $λ^3 − 2λ^2 + λ − ...
0
votes
1answer
15 views

Matrix for a recurrence

The matrix for a recurrence of the form $a_{k+2} = ka_{k+1}+a_{k}$ where $a_0 = 0$ and $a_1 = 1$ is given by $$\begin{bmatrix}k & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} a_{k+1} & a_k \...
3
votes
0answers
49 views

little Fermat theorem generalization proof without Burnside's lemma

Burnside's Lemma Deduce That: $$\sum_{i=1}^n a^{gcd(i,n)} $$ is divisible by $n$ it's a beautiful result. but i want to prove it without any abstract algebraic tools such as Burnside's Lemma... is ...
-2
votes
1answer
23 views

Any Mersenne prime contains two consecutive 9 digits? [on hold]

The kids with me were each asked to pick a number. It crossed my mind that a smart aleck might answer with a description of some number that we have never actually computed. I remembered that a ...
68
votes
10answers
12k views

Nice proofs of $\zeta(4) = \pi^4/90$?

I know some nice ways to prove that $\zeta(2) = \sum_{n=1}^{\infty} \frac{1}{n^2} = \pi^2/6$. For example, see Robin Chapman's list or the answers to the question "Different methods to compute $\sum_{...
31
votes
3answers
2k views

Does the equation $x^4+y^4+1 = z^2$ have a non-trivial solution?

The background of this question is this: Fermat proved that the equation, $$x^4+y^4 = z^2$$ has no solution in the positive integers. If we consider the near-miss, $$x^4+y^4-1 = z^2$$ then this has ...
4
votes
1answer
45 views

Determining when ring of integers is $\mathbb{Z}[\theta]$

Something which is not difficult to prove is that if $K$ is a number field generated by an integer $\theta$, then the ring of integers $\mathfrak{O}_K$ is generated over $\mathbb{Z}$ by $\theta$ and ...
3
votes
1answer
76 views

Algorithms for finding the ring of integers

In the book's Algebraic Number theory, Ian StewarT, Third edition (page 51-52), has the following propositions: Theorem 2.20: Let $G$ be an additive subgroup of $\mathfrak{O}_K$ of rank equal to the ...
7
votes
1answer
95 views

Show that the ring of integers $A$ of the cubic field $\mathbb Q[x]$ with $x^3=2$ is principal.

Show that the ring of integers $A$ of the cubic field $K=\mathbb Q[x]$ with $x^3=2$ is principal. The hint given in the book is to majorize the discriminant of $A$ by $D(1,x,x^2)$ and then use the ...
-3
votes
1answer
165 views

Again near at Riemann hypothesis [closed]

Let $\zeta(s)$ be Riemann extended zeta function for $Re(s)>0$. Let $\eta(s)$ be Riemann alternated zeta function for $Re(s)>0$, i.e. , $$ \eta(s)=\sum_{n=1}^{\infty}\frac{(-1)^{n+1}}{n^s}=...
1
vote
2answers
51 views

Find the maximum value that the quantity $2m+7n$ can have

Find the maximum value that the quantity $2m+7n$ can have such that there exist distinct positive integers $x_i$ $(1 \leq i \leq m)$, $y_j$ $(1 \leq j \leq n)$ such that the $x_i$'s are even, the $y_j$...
4
votes
1answer
32 views

Non-negative integer solutions to $4ab-a-b=c^2$

The puzzle is as follows: Problem: Find all non-negative integer solutions to $4ab-a-b=c^2$ My Progress: There is, of course, the trivial solution of $a=b=c=0$, and I suspect there are no more (...
1
vote
2answers
62 views

Generating function for $\sum_{n=0}^{\infty} n^{p} x^n$

I am trying to derive the generating function for $H(x,p) = \sum_{n=0}^{\infty} n^p x^n$ I am trying to solve it with the following logic: (Edited now, trying a new framing) Base case: $$H(x,0) = \...
1
vote
2answers
37 views

Dirichlet inverse of $(-1)^n$

I was tinkering around and noticed the Dirichlet inverse of $\,f(n) = (-1)^n$ seems to be $$ f^{-1}(n) = -\mu\!\left(n\,/\,2^{\nu_2(n)}\right)\left\lceil 2^{\nu_2(n)-1} \right\rceil, $$ where $\nu_p(n)...
4
votes
2answers
63 views

Growth of $\pi(2x) - 2\pi(x)$

In Hardy & Wright's Theory of Numbers (p. 494f in 6th ed.) there's a little discussion following the proof of the prime number theorem. We have $$ \pi(2x) - \pi(x) = \frac{x}{\log x} + o\...
1
vote
3answers
38 views

The number of $n$-tuples of nonnegative integers $(x_1,\ldots,x_n)$ satisfying the equation $x_1+\cdots+x_n = r$

For given positive integers $r,v,n$ let $S(r,v,n)$ denote the number of $n$-tuples of nonnegative integers $(x_1,\ldots,x_n)$ satisfying the equation $x_1+\cdots+x_n = r$ and such that $x_i \leq v$ ...
0
votes
0answers
33 views

For prime >2, is there always a power of a prime which is a primitive root? [closed]

As the title, I'm trying to find the answer about this question. However, I can't google anything :( Thanks! EDIT: this primitive root must less than the prime
31
votes
7answers
5k views

How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?

It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian ...
5
votes
1answer
46 views

Are the extremas of $h(x)$ global?

It is well known that $li(x)$, the integral logarithm is a very good approximation of $\pi(x)$, the nunmber of primes not exceeding $x$. So, a very good approximation for the probability, that a ...
3
votes
2answers
69 views

Find the common divisors of $a_{1986}$ and $a_{6891}$

Let $(a_n)_{n \in \mathbb{N}}$ be the sequence of integers defined recursively by $a_0 = 0$, $a_1 = 1, a_{n+2} = 4a_{n+1}+a_{n}$ for $n \geq 0$. Find the common divisors of $a_{1986}$ and $a_{6891}$. ...
1
vote
0answers
56 views

Induction Method in a special case of $ n!+1 = m^2 $ (Brocard's Problem)

Context: Brocard's problem is a problem in mathematics that asks to find integer values of $n$ and $m$ for which$$ n!+1 = m^2 \tag{1}$$ Let's define, $$T=\left(\left\lfloor \frac{ (\lfloor\log(n) \...
-2
votes
1answer
120 views

$\sqrt 1+\sqrt 2 +\sqrt 3 +\cdots +\sqrt {2009}$ change a sign to be rational [closed]

I have this problem: $$\sqrt 1+\sqrt 2 +\sqrt 3 +\cdots +\sqrt {2009}$$ Prove that you need to change ONLY a sign (to convert a $+$ to $-$) of a single square root, for the sum to be rational. EDIT:...
1
vote
3answers
137 views

If $n$ is an integer then $\gcd(2n+3,3n-2)=1\text{ or ?} $

There are two possible Gcd's for integers of the form, $2n+3$ and $3n-2$ I know the gcd is $1$ if I take the equation modulo $2$. However if I take the equation modulo $3$ I get, $2n$ and $-2$. ...
4
votes
1answer
64 views

What is the computational complexity of calculating $\pi(x)$ exactly?

The prime counting function $\pi(x)$ has been determined for $x=10^{26}$. The list of the $10^n$-th primes , however , ends at $n=18$. The $10^{18}$-th prime has $20$ digits. Apparantly, the ...
2
votes
0answers
71 views

A test problem about algebraic integers in complex field

In a recent algebraic test, I meet this problem: Let R be the ring of algebraic integers in C, K is the field of algebraic numbers in C. Let a be an element of K such that the ring R[a] is ...
1
vote
1answer
112 views

Siegel's Lemma for two solutions

Consider the homogeneous diophantine equation $$ax_1+bx_2+cx_3=0$$ over $\mathbb{Z}$ with a, b, c coprime. (A version of) Siegel's Lemma states, that there exists a non-trivial solution $x$, such ...
5
votes
2answers
181 views
+50

Find last 5 significant digits of 2017!

Since there are less powers of $5$ than of $2$ and since $10 = 2 \cdot 5$, I counted the number of zeros in $2017!$: $\left \lfloor{ \frac{2017}{5^1}}\right \rfloor + \left \lfloor{ \frac{2017}{5^2}}\...
22
votes
2answers
645 views

Proof of $\sum_{n=1}^{\infty}\frac1{n^3}\frac{\sinh\pi n\sqrt2-\sin\pi n\sqrt2}{{\cosh\pi n\sqrt2}-\cos\pi n\sqrt2}=\frac{\pi^3}{18\sqrt2}$

Show that $$\sum_{n=1}^{\infty}\frac{\sinh\big(\pi n\sqrt2\big)-\sin\big(\pi n\sqrt2\big)}{n^3\Big({\cosh\big(\pi n\sqrt2}\big)-\cos\big(\pi n\sqrt2\big)\Big)}=\frac{\pi^3}{18\sqrt2}$$ I have no ...
-1
votes
0answers
30 views

How large number does it take to give a counterexample in number theory? [closed]

There are many hypotheses in number theory regardless of the truth. I want to know how large number it needs to show a counterexample of certain hypothesis and how large number super-computers can ...
14
votes
1answer
715 views

How many digits of the googol-th prime can we calculate (or were calculated)?

Here, a lower and upper bound for the $n$-th prime are given. Applying the given bounds $$n(\ln(n\cdot\ln(n))-1)<p_n<n\cdot\ln(n\cdot\ln(n))$$ and the approximation $$p_n\approx n(\ln(n\...
0
votes
2answers
57 views

$(1^n+2^n+3^n+4^n)\mod5$ and using euler totient function to solve this

The problem gives us an integer $n$ which can be extremely large (can exceed any integer type of your programming language) and we need to calculate the value of the given expression . $$(1^n+2^n+3^n+...
4
votes
3answers
112 views

Books for maths olympiad

I want to prepare for the maths olympiad and I was wondering if you can recommend me some books about combinatorics, number theory and geometry at a beginner and intermediate level. I would appreciate ...
2
votes
2answers
42 views

Assuming $a_0 = 0$, $a_1 = 1$, and $ a_{n+2} = 4a_{n+1}+a_{n}$ for $n \geq 0$, prove that $\gcd(a_m,a_{m+1}) = \gcd(a_m,a_{m-1})$

Let $(a_n)_{n \in \mathbb{N}}$ be the sequence of integers defined recursively by $a_0 = 0$, $a_1 = 1$, and $a_{n+2} = 4a_{n+1}+a_{n}$ for $n \geq 0$. Prove that if $\gcd(a_m,a_{m+1}) = d > 1$, ...
3
votes
5answers
239 views

Find a positive integer solution to $xyzw=504(x^2+y^2+z^2+w^2)$

Find positive integer values of $x,y,z,w$, such that $$xyzw=504(x^2+y^2+z^2+w^2)$$ I found it at some point and now I am unable to find the solution anymore, maybe this equation isn't satisfiable? ...
1
vote
1answer
55 views

Strange results in mersenne.org database

I am interested in GIMPS project. I was browsing through known Mersenne prime numbers when I discovered strange records in their database. For example, M6972593 is the 38th Mersenne prime. However, ...
1
vote
3answers
34 views

If $p$ and $q$ are odd, prove that there are no integral solutions

Prove that if $p$ and $q$ are odd numbers , then the equation $x^{10} + p x^{​9} + q = 0$ does not have integral solution. Could some hint a simple approach to solve this question. I am not getting ...
0
votes
1answer
47 views

Prove that $\text{ord}_{2^n}(x) = 2^k$

Let $p$ be a prime. Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but $p^{n+1} \nmid x$. Prove that if $v_2(x^{2^k}-1) = n$ where $\gcd(x,2^n) = 1$, then $\text{ord}_{2^n}(x) = 2^k$. ...
1
vote
2answers
187 views

Largest number definable

If $a_n$ is defined as the largest integer definable using $n$ characters in some standard theory like PA or $Z_2$. Can we prove or disprove that there is some finite integer $k$, such that for all $...
17
votes
2answers
433 views

Conjectured closed form for $\sum_{n=-\infty}^\infty\frac{1}{\cosh\pi n+\frac{1}{\sqrt{2}}}$

I was trying to find closed form generalizations of the following well known hyperbolic secant sum $$ \sum_{n=-\infty}^\infty\frac{1}{\cosh\pi n}=\frac{\left\{\Gamma\left(\frac{1}{4}\right)\right\}^2}{...
6
votes
1answer
198 views

$m^2+2017=n^3$ has no solutions

Show that $m^2+2017=n^3$ has no solutions for positive integers $m,n$. I'm having trouble tackling this one, especially since $\mathbb{Z}[\sqrt{-2017}]$ isn't a UFD. We can write the equation as $m^...
1
vote
1answer
29 views

Find the gcd of the following Gaussian integers

$\gcd(5 + 8i, 3 + 2i)$ in $Z[i]$. I found it and I got 1 then I look at the manual solution and it turns out it can be i or -i or -1 or 1. why?
0
votes
0answers
12 views

Distribution of numbers of the form $p^{q-1}$, p and q prime

Prime numbers are exactly the integers having 2 divisors and of course, 2 is itself prime. If one considers the set of positive integers with a prime number of divisors, one can easily figure out that ...
1
vote
1answer
43 views

Prove that the Area of triangle whose vertices are $(0,0)$, $(b,a)$ and $(x,y)$ is $|by-ax|/2$

Prove that the Are of triangle whose vertices are $(0,0)$, $(b,a)$ and $(x,y)$ is $\displaystyle \frac{|by-ax|}{2}$. I found this problem in Number theory by George Andrews, but I wonder how it ...
4
votes
0answers
60 views

How many subsets of $n$ linearly independent binary strings of length $n$?

Let's consider binary words of length $n$ with elements {-1,1}. There are $2^n$ binary words of length $n$. Now let's consider a subset of $n$ such binary words. All possible subsets are $\binom{2^n}{...
0
votes
1answer
32 views

Mapping finite discrete numbers to the infinite set

This is an extension of my earlier question: Mapping discrete numbers Given that we can "map" $\mathbb{N}$ to $\mathbb{Z}$ via a bijection, I then wondered if it is possible to map a small subset of $\...
3
votes
1answer
92 views

Is there an elliptic curve with exactly one rational point?

Let $E$ be an elliptic curve defined over $\mathbb{Q}$. Is there an example of such an $E$ such that the only rational point in $E(\mathbb{Q})$ is the point at infinity? In other words, consider the ...
1
vote
0answers
36 views

Factors vs distinct factors

I have a doubt in questions where we are asked to find the number of distinct factors of a number. Do we have to consider the total number of factors which are positive factors + negative factors ...