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)

3
votes
1answer
86 views

What the rest of the division $5^{21}$ by $127$?

What the rest of the division $5^{21}$ by $127$?
3
votes
1answer
426 views

Number of samples to predict the next number in a pseudorandom number generator

Let: $$R_{n+1} = (mR_n + b) \bmod{a} $$ Assume we know the values of $R_1, R_2, \ldots, R_L $. What is the minimum value of $L$ (if it exists) such that we can determine $R_0, m, b$ and $a$?
3
votes
1answer
71 views

Why is the Jacobi symbol in this setting a unique homomorphism?

If $D \equiv 0,1$ mod $4$ a nonzero integer, why is the map given by $\chi: (\mathbb Z / D\mathbb Z)^* \rightarrow \{-1,+1\}, \chi([p]) = (D/p)$ for odd primes $p$ not dividing $D$, a unique ...
3
votes
3answers
121 views

Raising a rational integer to a $p$-adic power

Let $p$ be a prime number and $d$ a positive integer. If $n\in \mathbb{Z}_p$ (the ring of $p$-adic integers) how would one define $d^n$? Under what conditions would this be an element of ...
3
votes
0answers
87 views

An intuitive interpretation of Montgomery pair corrlation function vs. prime divisibility?

Theorem - If the Riemann hypothesis would be true, and the Montgomery pair correlation conjecture (see linked article page 183-184) true too; let $p \in \Bbb P$ prime, $n \in \Bbb N$ and $$\mathcal ...
3
votes
4answers
261 views

Sum of greatest common divisors

As usually, let $\gcd(a,b)$ be the greatest common divisor of integer numbers $a$ and $b$. What is the asymptotics of $$\frac{1}{n^2} \sum_{i=1}^{i=n} \sum_{j=1}^{j=n} \gcd(i,j)$$ as $n \to \infty?$
3
votes
3answers
542 views

No members of a sequence is a perfect square [duplicate]

Prove that no member of the sequence 11, 111, 1111, ... is a perfect square. I noticed that the first four terms of the sequence (above) are none of them are a perfect square. But I do not know what ...
3
votes
1answer
119 views

How can 0.149162536… be normal?

I was reading about normal numbers on WikiPedia, and I ran across this statement: Besicovitch (1935) proved that the number represented by the same expression, with f(n) = n^2, ...
3
votes
1answer
79 views

Congruence between Bernoulli numbers

I fell on the following fact as a by-product: If p is a prime number, then the sum of the Bernoulli numbers, from index 0 to p - 2, is congruent with - 1 modulo p. Do you know a simple proof ? ...
3
votes
1answer
83 views

Calculating Pythagorean triples

If $x$ and $y$ are even, then of course $z$ is too, and $\left(\frac{x}{2}, \frac{y}{2}, \frac{z}{2} \right)$ is also a Pythagorean triple. For this question we assume that $(x, y, z)$ is a ...
3
votes
1answer
236 views

Reasoning about the Chebyshev functions: How does one check an upper bound based on the second Chebyshev function?

In Ramanujan's proof of Bertrand's Postulate, Ramanujan states: $\log([x]!) - 2\log([\frac{1}{2}x]!) \le \psi(x) - \psi(\frac{1}{2}x) + \psi(\frac{1}{3}x)$ where: $\vartheta(x) = \sum_{p \le x} ...
3
votes
2answers
343 views

Factorization of ideals in $\mathbb{Z}[\sqrt{5}]$

Consider the ring $R=\mathbb{Z}[\sqrt{5}]$. Let $I$ be the following ideal of $R$: $$I:=(3,1+\sqrt{5})$$ My teacher said that the following equation holds: $$I^2=(3)I,$$ but I actually can't ...
3
votes
0answers
205 views

Explicit Formula

In the explicit expression for $$\psi_0(x) = x - \sum_{\rho} \frac{x^{\rho}}{\rho} - \frac{\zeta'(0)}{\zeta(0)} - \frac{1}{2} \log (1-x^{-2}) $$ $ x^\rho$ denotes $x^{\mathrm{Re} \rho}$. I wanted to ...
3
votes
1answer
102 views

Understanding a very elementary property of factorials

I've seen this stated in a few places. If $$\vartheta(x) = \sum_{p\le{x}} \log (p) \qquad \psi(x) = \sum_{m=1}^{\infty}\vartheta\left(\sqrt[m]{x}\right)$$ Then $$\log(x!) = \sum_{m=1}^{\infty} ...
3
votes
3answers
116 views

Hensel Lifting and solving with mods

I need to use the Hensel-Newton method (aka Hensel Lifting) to find all solutions of: $$x^2 + x + 47 \equiv 0\:(\text{mod } 343)$$ Note: $$ 343 = 7^3 $$ I don't really understand Hensel Lifting so ...
3
votes
3answers
2k views

show if these Gaussian integers are irreducible or not

Gaussian integers are the set $\mathbb{Z}[i]$ such that $\mathbb{Z}[i] = \{ a + bi | a, b \in \mathbb{Z} \}$. Unique factorisation does hold over the Gaussian integers. (a) Which of the following are ...
3
votes
1answer
192 views

Chebyshev function identity

given the Chebyshev function $$ \sum_{n \le x} \Lambda (n) = \Psi (x) $$ with $$ \Lambda (n) = \log p $$ for $ n=p^{k} $ and $ 0 $ otherwise is then true that (i think i saw it in apostol book) ...
3
votes
2answers
222 views

gcd as positive linear combination

Good evening, I have a question concerning the euclidean algorithm. One knows that for $a_1 , \ldots , a_n \in \mathbb{N} $ and $k\in \mathbb{N} $ there exist some $\lambda_i \in \mathbb{Z}$ such ...
3
votes
1answer
265 views

How to calculate Euler totient from nearby values?

I know that Euler totient function is multiplicative, that is $\phi(mn) = \phi(m) * \phi(n)$. And obviously it would't have additive feature. So i'm looking for any existing formula which facilitate ...
3
votes
0answers
75 views

Evaluating a sum [duplicate]

Possible Duplicate: Evaluating a power series Can somone help me find a closed form expression for this sum given any rational value of x, and any integer p, where {x} denotates the ...
3
votes
1answer
522 views

how to find integer solutions for $axy +bx + cy =d$?

How can I find the integer solutions for the diophantine equations $axy +bx + cy =d$ ? the smallest particular solution ($x_0$,$y_0$) and a way to generate the rest.
3
votes
3answers
1k views

Primes in Gaussian Integers

Let $p$ be a rational prime. It is is well known that if $p\equiv 3\;\;mod\;4$, then $p$ is inert in the ring of gaussian integers $G$, that is, $p$ is a gaussian prime. If $p\equiv 1\;mod\;4$ then ...
3
votes
3answers
195 views

Show that there exists infinitely many numbers that are coprime pairwise, in the set defined as following [duplicate]

The set $A$ = {$X_n\mid n\in \Bbb N$} where $X_n = a^{n+1} + a^{n} - 1$, with $a \gt 1, a \in \Bbb Z$. Show that there are infinitely many numbers that are pairwise coprime.
3
votes
4answers
1k views

Prime, followed by the cube of a prime, followed by the square of a prime. Other examples?

The numbers 7, 8, 9, apart from being part of a really lame math joke, also have a unique property. Consecutively, they are a prime number, followed by the cube of a prime, followed by the square of a ...
3
votes
1answer
749 views

Estimate for the product of primes less than n

In this paper Erdős shows a shorter proof for one of his old results stating that $$ s(n) = \prod_{p < n} p < 4^n$$ where the product is taken over all primes less than $n$. He also remarks that ...
3
votes
1answer
36 views

How can we show $1+ord_{p}n \le 2^{ord_{p}n} \le p^{(ord_{p}n)/x}$

$1+ord_{p}n \le 2^{ord_{p}n} \le p^{(ord_{p}n)/x}$ for $p> 2^{x},n\ge 2 \in \mathbb{N}$; $x>0 \in \mathbb{R}$ It was written here that this is clearly the case; I don't see it. Does somebody see ...
3
votes
2answers
250 views

Proofs from the BOOK: Bertrand's postulate Part 3: $\frac{2}{3}n<p \leq n \rightarrow$ no p divides $\binom{2n}{n}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 9: I have to show, that for $\frac{2}{3}n<p \leq n$ there is no p which divides ...
3
votes
1answer
272 views

If two primes differ by $n$, then infinitely many primes differ by $n$

A proof I'm writing rests on something I can't prove, probably beyond my knowledge, but it seems right: For any two primes $p_k, p_l$ (not necessarily consecutive) such that the distance between ...
3
votes
1answer
253 views

systems of congruences and CRT

I want to establish an efficient method to solve linear congruences to prove the Chinese Remainder Theorem. I need a proper generalization/proof for the following ones to go to further developments. ...
3
votes
2answers
202 views

Prove or refute that $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$

I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first. The problem is straight for you have and 3 ...
3
votes
2answers
368 views

Where is the mistake in this incorrect proof in Eisenstein integers?

The Diophantine equation is $n^2 + n + 1 = m^3$ my attempt to solve it shows there is no solutions to this equation, but in fact there are four. I could not find my mistake so I hope someone could ...
3
votes
1answer
214 views

Recurrence representation(s): $a(n+1)=a(n)(n-1/2)+o(1/n)$ and $a(n+1)=a(n)(n-1/2+o(1/n))$

I know that the recurrence $\displaystyle a(n+1)=a(n)(n-1/2)$ can be represented like $\displaystyle \frac{(2n-1)!!}{2^n}$ Actually the initial recurrence is slightly different: $$\displaystyle ...
3
votes
1answer
474 views

How to prove Pell's equation for a specific case?

My problem is proving $x^2 - 13y^2 = 1$ has integers solutions. I can find easily see that (+-1, 0) are trivial solution. My question is: is it sufficient to complete the proof? How can I approach ...
3
votes
2answers
272 views

Ramanujan congruences and étale cohomology

What is a good reference for the story of congruences such as $$\displaystyle \tau(n) \equiv \sigma(11)(n) \mod\ 691$$ with a conceptual explanation with connections to étale cohomology, etc?
3
votes
3answers
1k views

$n^2 + 3n +5$ is not divisible by $121$

Question: Show that $n^2 + 3n + 5$ is not divisible by $121$, where $n$ is an integer.
3
votes
2answers
358 views

Liouville's number revisited

Liouville's Number is defined as $L = \sum_{n=1}^{\infty}(10^{-n!})$. Does it have other applications than just constructing a transcendental number? (Personally, I would have defined it (as ...
2
votes
0answers
85 views

$(z-k)$ is composite then $(z-1)+(k-1)$ is also composite(A proof for composite number).

Given $z(z-1)$ is divisible by all prime $< n$ where $ n>\sqrt z$ $(z+k)$ is prime. Prove or disprove if $(z-k)$ is composite then $(z-1)+(k-1)$ is also composite. ...
2
votes
0answers
70 views

Number of solutions of arithmetic function's equation [duplicate]

Say, an equation is given below \begin{equation} 2\pi(x) - \pi(2x)=\omega(x) \end{equation} where $x$ is a positive integer, $\pi(x)$ is the prime-counting function, and $\omega(x)$ is the number of ...
2
votes
1answer
55 views

writing $pq$ as a sum of squares for primes $p,q$

Let $p$ and $q$ be distinct primes congruent to $1$ mod $4$. How many ways are there to write $pq$ as a sum of squares? I know that any prime $p\equiv 1\pmod 4$ can be written uniquely as a sum of ...
2
votes
2answers
85 views

Show that $4^n + n^4$ is always composite $\forall n > 1$ [duplicate]

I have to show that: $4^n + n^4$ is always composite $\forall n > 1$. I know that composite numbers are integers greater than one but not prime, but I am finding difficult to solve this ...
2
votes
2answers
78 views

Clever use of Pell's equation

Find infinitely many triples $(a,b,c)$ of positive integers such that $a,b,c$ are in arithmetic progression and such that $ab+1$, $bc+1$, and $ca+1$are perfect squares. The solution is: Consider the ...
2
votes
0answers
80 views

Any formula for the exact number of primes below a given bound?

Reading The music of the primes, the author relates that Riemann had figured out a formula giving exact number of primes up to a certain bound with no errors. Does such formula really exist? If ...
2
votes
1answer
100 views

Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair

Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of ...
2
votes
1answer
66 views

Numbers which are not the sum of distinct squares

We are defining square factorization as representation a positive natural number as sum of squares of different positive, integer numbers. For example $5 = 1^2 +2^2$ and $5$ has no more ...
2
votes
0answers
69 views

Any heuristic explanation on why sieve methods can not prove Goldbach conjecture?

Any heuristic explanation on why sieve methods can not prove strong Goldbach conjecture ? I remember that Terence Tao published a blog and gave an heuristic explanation on why circle methods very ...
2
votes
1answer
89 views

Prime representable as $ x^2 + 3y^2 $

I'm to prove that if $ p = 3k+1 $ is a prime greater than $ 3 $ then there exist $ x,y \in \mathbb{Z} $ such that $$ p=x^2 + 3y^2 $$ I just don't know how to begin. All I have is Thue lemma and it ...
2
votes
2answers
90 views

Can Andrica's conjecture be proven by proving a tighter upper bound for prime gaps?

I checked some differences between square roots of various natural numbers and I am wondering what is required to prove Andrica's conjecture. Would a tighter upper bound for the prime gap above $n$ be ...
2
votes
0answers
47 views

Number of divisiors of $n$ less than $m$

I'm looking for a closed- or alternative-form of the function that counts the number of divisors of an integer $n$ that are less than some integer $m$ (interested in $m < n$, obviously): $ ...
2
votes
2answers
212 views

Solutions of Diophantine equation

Does there exists any other solutions of the following Diophantine equation $$zx^2 +xy^2 +yz^2 =xyzt .$$ I found that $$(x,y,z,t) =(s,s,s,3) ,(x,y,z,t)=(s,2s,4s ,5)$$ where $s\in\mathbb{N}$ are ...
2
votes
2answers
138 views

How find the value $\beta$ such $\left|\frac{p}{q}-\sqrt{2}\right|<\frac{\beta}{q^2}$

Find all positive real number $\beta$,there are infinitely many relatively prime integers $(p,q)$ such that $$\left|\dfrac{p}{q}-\sqrt{2}\right|<\dfrac{\beta}{q^2}$$ maybe this problem background ...