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
1answer
9 views

Generate Sieve of Eratosthenes without “sieve” (generate prime set in interval)

How do I generate a list of primes based on the Sieve of Eratosthenes? I mean by excluding the divisible numbers beforehand, which is tricky for large numbers. I am an number theory amateur, but was ...
5
votes
1answer
292 views
+100

Conjecture about primes and the factorial

Below $0\notin\mathbb N$. Further corrected conjecture: For all prime numbers $p>5$ there exist a prime number $q<p$ such that $q\equiv m!\!\pmod p$, $2<m<p$. or Given a prime ...
2
votes
2answers
77 views

Finding Pythagorean triplet given the hypotenuse

I have a number $c$ which is an integer and can be even or odd. It is the hypotenuse of a right angled triangle. How can I find integers $a,b$ such that $$ a^2 + b^2 = c^2 $$ What would be the ...
1
vote
3answers
32 views

Solve the congruence $6x+15y \equiv 9(mod 18)$

Solve the congruence $6x+15y \equiv 9(mod 18)$ Approach: $(6,18)=6$, so $$15y \equiv 9(mod\text{ } 6)$$ $$15y \equiv 3(mod\text{ } 6)$$ So the equation will have $(15,6)$ solutions. Now we divide ...
1
vote
2answers
43 views

Sixth digit after the decimal point

Determine the sixth number after the decimal point in the number $(\sqrt{1978} +\lfloor\sqrt{1978}\rfloor)^{20}$ I don't understand in the below how they get $y<\frac{1978-1936}{2 \cdot 44}$. Can ...
1
vote
0answers
20 views

How to show that for n sufficiently large, relative to k, (n+1)(n+2)…(n+k) is divisible by at least k distinct primes

I would like to show that (n+k)!/n! is divisible by at least k distinct primes whenever n is sufficiently large. We all know that it is divisible by k! and hence by pi(k) ~ k/log k distinct primes, ...
1
vote
1answer
33 views

Solving the Diophantine equation $t^n + 2 \equiv 0 \bmod s^n - 1$

My problem is this. find the maximal integer n, so the equation: $t^n+2\equiv0 \mod (s^n-1). $ has a solution (s,t>1 have to be integers). I would like to read your solution and even just an opinion....
2
votes
1answer
26 views

Suppose $a,b,c > 0$. Then there are finitely many integer $x,y$ with $a^x > cb^y$.

Here is the question: For this question, it says to find finitely many positive numbers pairs of x and y for to fulfill the inequality. My thought is when [A] bigger than 1 or b is smaller than 1, ...
5
votes
1answer
166 views

Number Theory Characterization Problem

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, let us associate to it the set $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. We're going to define a d-self-contained number as any natural number ...
2
votes
1answer
64 views

Explaining a Series Expansion for the Divisor Function

The "sum-of-divisors" function, defined as $\sigma(n)=\sum_{d\,\mid\,n}d$, can be expressed as $$\sigma(n)=\sum_{i=1}^n\sum_{j=1}^i\cos\Big(2\pi n \frac{j}{i}\Big)$$This expansion makes logical sense. ...
3
votes
1answer
12 views

Turing Decryption Example

I know this exact same question exists but I am still having problems in understanding it. The following is given in the text: The message m can be any integer in the set {0,1,2,…,p−1}; in par­...
2
votes
1answer
42 views

A natural number written as an arithmetic progression

Let $a$ and $n>1$ be positive integers and $$x = a+(a+1)+\cdots+(a+n-1) = \dfrac{n(2a+n-1)}{2}$$ where $x$ is also a positive integer. Prove that there exist $a,n$ if and only if $x$ has an odd ...
0
votes
0answers
13 views

Divisor Function over a Quadratic

The divisor function is defined as $\sigma_1(n)=\sigma(n)=\sum_{d\mid n}d$. Consider the divisor function over a quadratic $$f(x)=\sigma(a x^2+bx+c)$$ Where $a,b,c \in \mathbb{Z}$ (note we allow $a, b$...
-3
votes
0answers
26 views

how to solve this manually with using scientific calculator— (2.0012) raise to the power 107. [on hold]

How to solve this manually with using scientific calculator-- (2.0012) raise to the power 107.
0
votes
1answer
27 views

Smallest number $n$ for which $p\mid n!+1$ and $n\nmid p-1$

My question is that: What is the smallest positive integer $n$ such that $n!+1$ is divisible by $p$ and $p-1$ is not divisible by $n$ and give some examples for $n$ This is my question, I try to ...
0
votes
1answer
44 views

A question about pythagorean triples

Recently, I was given a problem, which was to find two sets of points on the graph $y = x^2$ that have a rational distance from each other. I was then told, if I couldn't find any, to try and prove ...
-1
votes
1answer
48 views

Numbers not expressible as a sum of an arithmetic progression

For every integer $d \geq 1$, let $M_d$ be the set of all positive integers that cannot be written as a sum of an arithmetic progression with difference $d$, having at least two terms and consisting ...
7
votes
2answers
68 views

For which $n$ can $(a, nb, c)$ and $(b, c, d)$ be Pythagorean triples?

Fermat proved that if $(a, b, c)$ is a Pythagorean triple, then $(b, c, d)$ cannot be a Pythagorean triple. Suppose $(a, nb, c)$ form a Pythagorean triple. Can $(b, c, d)$ be a Pythagorean triple? ...
2
votes
1answer
20 views

How to prove a relation between the number of distinct prime factors, the Liouville function and the divisor function?

In a paper I was reading recently, the author has made use of the following formula in his proof: $\displaystyle\sum_{k|n}\lambda(k)=\displaystyle\sum_{k|n}2^{\nu(k)}\lambda(k)d\big(\frac{n}{k}\big)$....
1
vote
0answers
32 views
1
vote
4answers
58 views

If $x^2+y^2 \equiv 0\pmod{p}$, then $p \equiv 1 \pmod{4}$

Prove that if $x^2+y^2 \equiv 0\pmod{p}$ where $p$ is a prime and $x,y$ are not both divisible by $p$, then $p \equiv 1 \pmod{4}$. I tried using that $x^2 \equiv -y^2 \pmod{p}$ and conjectured that $...
1
vote
1answer
27 views

Number Theory Lemma About Linear Congruence (Explanation Needed)

I was reading Elementary Number Theory Second Edition by Dudley Underwood, and I came across what appeared to me to be a contradiction in chapter/section 5. The book says: If one integer satisfies $...
0
votes
1answer
19 views

Where $a, b$ coprime, does $ax + b$ generate infinitely many 2-almost primes, infinitely many 3-almost primes, etc.?

I've seen various references to Dirichlet's theorem on arithmetic progressions claiming that where $a, b$ coprime, $ax + b$ not only generates infinitely many primes, but also infinitely many ...
6
votes
1answer
111 views
+50

Solve in integers the equation $\sqrt{x^3-3xy^2+2y^3}=\sqrt[3]{13x+8}$

Solve in integers the equation $$\sqrt{x^3-3xy^2+2y^3}=\sqrt[3]{13x+8}$$ My work so far: I used www.wolframalpha.com. Then $x=9,y=8 -$ solution. My attempt: 1) Let $\sqrt{x^3-3xy^2+2y^3}=a, \...
2
votes
1answer
41 views

Showing that $c_{i}\equiv 0\pmod{p}$

Let the numbers $c_{i}$ be defined by the power series identity $$\frac{1+x+x^{2}+\ldots+x^{p-1}}{(1-x)^{p-1}}= 1+c_{1}x+c_{2}x^{2}+\ldots$$ Show that $c_{i}\equiv 0\pmod{p}$ for all $i\geq 1$. $\...
-1
votes
1answer
28 views

Proof about congruence and gcd

Show that if $gcd(a,b)=1$, then the congruence $ax \equiv k (mod$ $ b)$ has a solution $x$ for every integer $k$ if $gcd(a,b)=1$ then there exists integers x,y such that $$ax+by=1$$ then we multiply ...
0
votes
0answers
25 views

Number of distinct integer-valued vector solution for $x_1 + x_2 + … + x_r = n$ [duplicate]

The Number Of Integer Solutions Of Equations $$x_1 + x_2 + ... + x_r = n$$ An approach is to find the number of distinct non-negative integer-valued vectors $(x_1,x_2,...,x_r)$ such that $$x_1 + x_2 +...
1
vote
1answer
80 views

Legendre's Conjecture

I have read and heard conflicting reports about whether or not Legendre's conjecture has been proven. Refresh: Legendre believed that there will always be at least one prime between $n^2$ and $(n+1)^2$...
57
votes
2answers
3k views

Is this similarity to the Fourier transform of the von Mangoldt function real?

Mathematica knows that the logarithm of $n$ is: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ The von Mangoldt function should then be: $$\Lambda(n)=\...
0
votes
2answers
29 views

proving theorem about perfect powers

Im currently studying the journal entitled Perfect Powers with All Equal Digits but One theorem: For a fixed integer $l \geq 3$, there are only finitely many perfect $l$-th powers all whose digits ...
10
votes
1answer
237 views
+50

Solving $(n+1)(n+2)…(n+k)−k = x^2$

Let $n$ and $k$ be positive integers. Need to find all pairs of $(n,k)$ such that $$(n+1)(n+2) \cdots (n+k)−k = x^2,$$ where $x^2$ is a perfect square.
0
votes
3answers
29 views

Question about linear congruences

Consider the congruence $$2x+7y \equiv 5\pmod{12}$$ Here $(2,7,12)=1$. Since $(2,12)=2$, we must have $$7y \equiv 5\pmod{2}$$ Which clearly gives $y \equiv 1\pmod{2}$, or $y \equiv 1,3,5,7,9,11\...
2
votes
4answers
53 views

Positive integers $a$ and $b$ are such that $a+b=a/b + b/a$. Find $a^2+ b^2$.

Positive integers $a$ and $b$ are such that $$a+b=a/b + b/a$$ Find $$a^2+ b^2$$ My try:- Given that $$a+b=a/b + b/a$$On simplification we get $$a^2 b+ b^2 a= a^2 + b^2$$ But in my book the given ...
0
votes
0answers
10 views

Application of the EGZ theorem

Given $r$ numbers $a_1,a_2,...,a_r$ and $n=qP$ where $P$ is the product of these $r$ numbers. $q$ is a natural number such that $q \geq 2$. Also given is a matrix $A$ of the following form: $$A=\...
5
votes
1answer
143 views

Number of zeros in Fibonacci sequences mod $p$

We know that Fibonacci sequences are periodic in mod $m$. For example, for $p\equiv \pm 1 \pmod 5$ and $\pm 2 \pmod 5$ the periods for Fibonacci sequences modulo $p$ divide $p-1$ and $2p+2$ ...
5
votes
2answers
87 views

$\dfrac{x^2+y^2}{x+y}$ is a divisor of $1978$

Two nonzero integers $x,y$ (not necessarily positive) are such that $x+y$ is a divisor of $x^2+y^2$, and the quotient $\dfrac{x^2+y^2}{x+y}$ is a divisor of $1978$. Prove that $x = y$. Let $A = \...
2
votes
1answer
57 views

The first step in the proof of the Pólya-Vinogradov Inequality.

The well-known Pólya-Vinogradov Inequality states: $$\forall m, n \in \mathbb{N}: \displaystyle \left|{\sum_{k \mathop = m}^{m+n} \left({\frac k p}\right)}\right| < \sqrt p \ \ln p,$$ where $\...
0
votes
2answers
59 views

Solution of Diophantine equation

Find all integral solutions of $x^2+1= y^2+z^2$. Actually I have to find all integral solution of $a(a+1)=b(b+1)+c(c+1)$. I reduced this in the above form I.e., $ (2a+1)^2+1= (2b+1)^2+(2c+1)^2$ .
0
votes
2answers
46 views

Question about congruence

Find the smallest positive n that satisfies the system of congruences $$n \equiv 3 \pmod 4$$ $$n \equiv 4 \pmod5$$ $$n \equiv 5 \pmod 7$$ Approach: Not very useful $4|3-n$, $5|4-n$, $7|5-n$ $3-...
0
votes
2answers
34 views

Prove that if $p \equiv 3 \pmod{4}$ then $x^2+y^2 \not \equiv 0 \pmod{p}$

Let $x$ and $y$ be integers not congruent to $0$ modulo $p$ where $p$ is a prime. Prove that if $p \equiv 3 \pmod{4}$ then $x^2+y^2 \not \equiv 0 \pmod{p}$. I thought about proving this ...
1
vote
0answers
37 views

Given some arbitrary roots of a polynomial p(x,y,z,…) with integer coefficients, is it possible to tell if p has a root in the Gaussian integers?

I'm trying to find if p(x,y,z,...)=0 has a Gaussian integer root (more specifically, I want to find if p has a Gaussian integer root where the imaginary components are even, but if that can't be done, ...
2
votes
1answer
31 views

Explaining an integral involving the divisor function

In a 1973 paper by Martinet, Deshouilliers and Cohen, $A(x)$ is defined as $$A(x)=\lim_{N\to\infty}\frac{\#\{n\leq N\mid \frac{\sigma(n)}{n}≥x \}}{N}$$ where $\sigma(n)$ is the "sum-of-divisors" ...
0
votes
0answers
22 views

Is there a generalized method, algorithm, or even branch of mathematics for analyzing common characteristics of sets of ordered positive integers? [on hold]

For example, if we are given the following sorted list of positive integers: 5039747128897487 9122935449243496 11091242044881088 22811737014961532 34421747473277532 37961123093170048 ...
2
votes
0answers
43 views

Partitioning a set of integers (with Alice and Bob)

Let $ d_1,\ldots,d_n \in \mathbb{N}_{\ge 2} $ (not necessarily distinct) be given. Define $ D:=\operatorname{lcm}(d_1,\ldots,d_n) $ and $ d:=\sum_{i=1}^n d_i $. (1) Alice claims that whenever $ \...
4
votes
1answer
68 views

Find all odd positive integers $n$, which there exists odd positive integers $x_1,x_2,..,x_n$, such that $x_1^2+x_2^2+\cdots+x_n^2=n^4$

Find all odd positive integers $n$, which there exists odd positive integers $x_1,x_2,..,x_n$, such that $$x_1^2+x_2^2+\cdots+x_n^2=n^4$$ My work so far 1) $n=3$ $$x_1^2+x_2^2+x_3^2=81$$ no ...
0
votes
1answer
33 views

Are there more non-perfect square numbers than perfect squares?

Can anything be said on this issue? I was wondering if one can find a mapping such that the cardinality of two sets of perfect and non-perfect squares can be compared. Not sure if it's a good question ...