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

Find the number of Primes less than $2^{2^{100}}$

The number of primes less than $2^{2^{100}}$ is $(a)101$ $(b)100$ $(c) 2^{100}$ $(c)2^{101}$. How can I solve this ? Please help. Thank you.
0
votes
0answers
26 views

Number Theory Characterization Problem 2

Before proposing the problem itself, it shall be profitable to define $b_{p}(k) = k^{p}$. In other words, the sequence $b_{p}(k)$ is an arithmetic progression of order p. For the sake of our purposes, ...
1
vote
0answers
44 views

When is the polynomial $\prod\limits_{i=1}^n\,\left(x-a_i\right)+1$ reducible in $\mathbb{Z}[x]$?

This post is inspired by Prove that the polynomial $\prod\limits_{i=1}^n\,\left(x-a_i\right)-1$ is irreducible in $\mathbb{Z}[x]$.. (A) Find all positive integers $n$ and integers $a_1,a_2,\...
4
votes
1answer
32 views

Is every unramified extension of DVRs simple?

Let $A$ be a discrete valuation ring with maximal ideal $\mathfrak{m}$, fraction field $K$, and $L$ a finite separable extension of $K$ degree $n$, unramified w.r.t. $A$. Let $B$ be the integral ...
2
votes
3answers
74 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
1answer
33 views

The set of natural numbers that don't belong to a set

Describe which natural numbers do not belong to the set $$E = \left\{\left[n+\sqrt{n}+\frac{1}{2}\right] \mid n \in \mathbb{N}\right\}.$$ The answer is the set of positive perfect squares. I am not ...
1
vote
2answers
24 views

How many five-digit numbers are there that have number 4 as at least one digit?

How many five-digit numbers are there that have number 4 as at least one digit? How to do this? I don't know how to start.
4
votes
3answers
54 views

Positive integer solution to equation $(x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=15$

What is the total number of positive integer solution to the equation $(x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=15$ a) 20 $\qquad$ $\qquad$ $\qquad$ $\qquad$ b) 18 c) 10 $\qquad$ $\qquad$ $\qquad$ $\qquad$ ...
2
votes
2answers
5k views

RSA: Fast factorization of N if d and e are known

I stumbled across this paragraph in a paper: Hence, user b cannot decrypt C directly. But using e and d , user b can quickly factor N. How is it possible to speedup the prime factorization ...
1
vote
0answers
34 views

Can $\mathbb N$ can be partitioned into infinitely many subsets $A+b_k$ for some infinite $A$

I came across this fantastic mathematical result and I can't help but think that it's too amazing a result to not have a paper on it or at least be named after somebody ! Unfortunately, the book just ...
1
vote
1answer
40 views

Show that the cube roots of three distinct prime numbers cannot be three terms (not necessarily consecutive) of an arithmetic progression

I'm thinking we could do a contradiction, maybe showing that one of the primes is a composite number if they are in a sequence, but I'm not sure how to finish this up. I had this as a math problem in ...
0
votes
0answers
38 views

Is $p_1p_2p_3\cdots p_i > p_{i+1}^2$? [duplicate]

Is it always true that $p_1p_2p_3\cdots p_i > p_{i+1}^2$ where $p_i$ are the prime numbers listed in increasing order and $i>3$? I was wondering if this is true because it would seem to depend ...
1
vote
1answer
41 views

Is the Euler prime of an odd perfect number a repunit, or otherwise?

Let $N = {q^k}{n^2}$ be an odd perfect number given in Eulerian form (i.e., $q$ is prime with $\gcd(q,n)=1$ and $q \equiv k \equiv 1 \pmod 4$). (That is, $2N=\sigma(N)$ where $\sigma$ is the ...
2
votes
1answer
90 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$...
0
votes
2answers
47 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
vote
1answer
23 views

Question about properties of congruence

Why can we divide the following expression by $2$? $$24u \equiv -2 \pmod{17}$$ $$12u \equiv -1 \pmod{17}$$
6
votes
1answer
131 views

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, \...
3
votes
0answers
37 views

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

I would like to show that $\displaystyle \frac{(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 $\...
2
votes
1answer
89 views

What level of mathematics do I need to study the Collatz Conjecture?

I recently came across the Collatz Conjecture and I'm really intrigued by its tautological simplicity and complexity. I'm under no illusions that I can make any progress with a proof for it but I ...
1
vote
3answers
49 views

Solve the congruence $6x+15y \equiv 9 \pmod {18}$

Solve the congruence $6x+15y \equiv 9\pmod {18}$ Approach: $(6,18)=6$, so $$15y \equiv 9\pmod 6$$ $$15y \equiv 3\pmod 6$$ So the equation will have $(15,6)$ solutions. Now we divide by 3 $$5y \...
1
vote
1answer
19 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 ...
6
votes
1answer
307 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
81 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
1answer
34 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
173 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
67 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. ...
4
votes
1answer
21 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
47 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
14 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
29 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
32 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 ...
-1
votes
1answer
53 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
81 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
22 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
33 views

How to find a simple function with those very specific properties?

I'm looking for a function F : N -> N, for N < 10, such that: ...
1
vote
4answers
61 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
28 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 ...
2
votes
1answer
44 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
30 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 +...
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
30 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 ...
12
votes
1answer
263 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.
2
votes
4answers
54 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
11 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
88 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
60 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 $\...