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
3answers
560 views

Can we use Peano's axioms to prove that integer = prime + integer?

Every integer greater than 2 can be expressed as sum of some prime number greater than 2 and some nonegative integer....$n=p+m$. Since 3=3+0; 4=3+1; 5=3+2 or 5=5+0...etc it is obvious that statement ...
9
votes
1answer
310 views

Minimal solutions to $\sum a_i x_i = d$

Let $S = \{a_1, a_2, \ldots, a_n\}$ be a finite set of positive integers with $\gcd(a_1, a_2, \ldots, a_n)=1$, and let $d$ be any positive integer. Then $\sum_{i=1}^n a_i x_i = d$ is solvable in ...
1
vote
3answers
444 views

Patterns in Sequences

I've heard in a movie that for any sequence of numbers, there is a nice formula for generating that sequence. So, for example if I write: 1,2,1,2,3,3,1,2,3,1,2,4,... There is a formula for ...
3
votes
2answers
131 views

Proof that $a\equiv 1\,(\textrm{mod }8)$ implies $a$ is a square modulo $2^n$ for all $n$

I know some elementary proofs of this fact. I was wondering if there's some short slick proof of this fact using the structure of the $2$-adic integers? I'm looking for a proof of this fact that's ...
3
votes
1answer
204 views

Class field theory and writing down explicit fields

I'm taking a class in CFT and I'm trying to figure out what the theorems say and what they can be used for to get a "feel" for them. More explicitly, say I take $\mathbb{Q}_p$, so we have the local ...
3
votes
2answers
563 views

$\gcd$ proof relating to $\gcd$'s associativity and commutativity (I think)

I am trying to prove that the $\gcd(a,b,c)$ = $\gcd(\gcd(a,b),c)$. I think it has something to do with $\gcd$'s being able to be represented by a linear combination (that is $\gcd(a,b) = ax + by > ...
22
votes
1answer
830 views

Is it possible $n(n+1)(n+2)…(n+k)$ is a square?

Let $n,k$ two integers greater than $1$, is it possible that $n(n+1)(n+2)...(n+k)$ is a square $m^2$, with $m$ an integer ? Thanks in advance.
5
votes
3answers
258 views

Finding $p^\textrm{th}$ roots in $\mathbb{Q}_p$?

So assume we are given some $a\in\mathbb{Z}_p^\times$ and we want to figure out if $X^p-a$ has a root in $\mathbb{Q}_p$. We know that such a root must be unique, because given two such roots ...
1
vote
1answer
87 views

Given a function $f(x)$, is there an analytic way to determine which integer values of $x$ give an integer value of $f(x)$?

Basically, I have some function $f(x)$ and I would like to figure out which integer values of $x$ make it such that $f(x)$ is also an integer. I know that I could use brute force and try all integer ...
2
votes
1answer
926 views

CRC computation

I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation ...
13
votes
4answers
2k views

Beginner's text for Algebraic Number Theory

What's good book for learning Algebraic Number Theory with minimum prerequisites? Assume that the reader has done an basic abstract algebra course.
8
votes
2answers
329 views

Showing the equivalence of two forms of the Goldbach Conjecture

My number theory textbook has the following (paraphrased) exercise: Goldbach wrote a letter to Euler with the following conjecture: Every integer greater than five can be written as the sum of three ...
0
votes
1answer
1k views

solving modulo equation

How to solve this $$x^a \equiv b \pmod n$$ I need to be able to find $x$, given $b$. $a$ is always $23407534262244700$ and $n$ is $465992738619896000$. Someone mentioned I can use Fermat and ...
4
votes
0answers
708 views

Project Euler Problem 338

I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The ...
4
votes
2answers
425 views

Learning about partitions and modular forms

I'm interested in learning about partitions and modular forms. I already know algebra and analysis (complex and real). Can any one suggest me books or other materials from where I can learn these ...
2
votes
1answer
221 views

If a prime with prime norm is a split prime, in the number ring PID

If a prime with prime norm is a split prime , in an number ring PID? Example: $5-\sqrt{14}$ in $\mathbb{Z}[\sqrt{14}]$ has norm $11$, it is a split prime in $\mathbb{Z}[\sqrt{14}]$? Why? Thanks
12
votes
0answers
554 views

The radical solution of a solvable 17th degree equation

(The question is at the bottom of the post.) Here's a "natural" solvable 17-th deg eqn with small coefficients: $$\begin{align*} x^{17}-6 x^{16}&-24 x^{15}-42 x^{14}-31 x^{13}-23 x^{12}-7 ...
9
votes
1answer
543 views

The largest possible prime gap?

What is the largest possible prime gap if we observe only 1000-digits numbers? There are few conjectures about this question but is there something that we can say and be absolutely sure of it?
-1
votes
1answer
436 views

Doubt on class group

I started reading Class group after some one's advice ,so I got the following doubts,I would be happy if someone clarify the doubts, I understood that the class group measures the failure of the ...
4
votes
1answer
253 views

How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?

What is the most efficient algorithm for finding prime numbers which belongs to the interval $(p,p^2)$ , where $p$ is some arbitrary prime number? I have heard for Sieve of Atkin but is there some ...
13
votes
2answers
2k views

How to know if a number is a power of $x$

I couldn't find anything on the Internet which could direct me to the solution of the following problem. I want to know if $n$ can be calculated by $x^y$ where $y\ge 2$ and $x\ge 2$. I tried using ...
2
votes
1answer
199 views

Integers in $p$-adic field

Let $K$ be a finite extension of $\mathbb Q_p$. How to prove that if an element of $K$ has non negative valuation then it is algebraic over $\mathbb Z_p$? I would like also a reference for this proof ...
28
votes
3answers
612 views

Sequence of numbers with prime factorization $pq^2$

I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions: What is the ...
5
votes
3answers
472 views

Powers as a complete residue system modulo $p$?

Question 1. With $0 < a < p$, $p$ prime and $\gcd(a,p-1)=1$, is it true that $0, 1, 2^a, ...,(p-1)^a$ is a complete residue system modulo $p$? If not, will a similar statement hold? Question ...
7
votes
2answers
320 views

Summing the prime power counting function up to equal some value $n$

I want to find $c_k$ for $n = 1 + c_1 \Pi(n) + c_2 \Pi(\frac{n}{2})+ c_3 \Pi(\frac{n}{3})+ c_4 \Pi(\frac{n}{4})+ c_5 \Pi(\frac{n}{5})+...$, assuming there are such coefficients, where $\Pi(n) = ...
1
vote
1answer
253 views

Fixing Hasse principle

As everyone know that Hasse principle (I am referring to Hasse Local-Global Principle) doesn't work for cubics, but today my question is concerned about: Is there any method or any known theorem, ...
9
votes
2answers
237 views

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime?

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was ...
3
votes
1answer
121 views

Counting bases to which numbers are pseudoprime

Let $n=p_1^{a_1}\cdots p_k^{a_k}$ be an odd composite. Then the number of bases $1\le b\le n-1$ for which n is a strong pseudoprime is $$ \left(1 + \frac{2^{k\nu}-1}{2^k-1}\right) ...
6
votes
1answer
570 views

Are the primes found as a subset in this sequence $a_n$?

Below is a introduction that contains some background to my question. The question is found at the bottom. By calculating the eigenvalues of the matrix defined by the recurrence: $\displaystyle ...
4
votes
1answer
440 views

Even numbers greater than 10 as sum of two specific odd numbers

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved(or disproved) ,so my question is: Is it true that every even number ...
7
votes
1answer
130 views

Description of $R \otimes R$ for $R$ a ring of integers

If $K/k$ is a finite Galois extension of fields, with Galois group $G$, there's an isomorphism $$ K \ \otimes_k \ K \simeq \oplus_{\sigma_i \in G} \ K$$ given by sending $a \otimes b$ to $ (..., ...
19
votes
2answers
628 views

Asymptotic behaviour of sums of consecutive powers

Let $S_k(n)$, for $k = 0, 1, 2, \ldots$, be defined as follows $$S_k(n) = \sum_{i=1}^n \ i^k$$ For fixed (small) $k$, you can determine a nice formula in terms of $n$ for this, which you can then ...
8
votes
2answers
511 views

Why is this sum equal to the Logarithmic Integral?

I am using this sum: $$\sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}\left((-1)^{k-1} (n-1) + \sum_{j=1}^{k-1}\frac{(-1)^{j+k-1}n (\log n)^j}{j!}\right)$$ Empirically, this is precisely equal to ...
21
votes
8answers
2k views

Intuition behind “ideal”

To briefly put forward my question, can anyone beautifully explain me in your own view, what was the main intuition behind inventing the ideal of a ring? I want a clarified explanations in these ...
2
votes
2answers
840 views

Bound for divisor function

I have been searching for a bound of the divisor function $d(n)$, meaning the number of divisors of n. So far I have found that it can be bounded by $$ d(n) \le e^{O(\frac{\log n}{\log \log n})}$$ ...
12
votes
7answers
10k views

Is a prime factor of a number always less than its square root?

I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for ...
1
vote
1answer
133 views

Checking if all elements are prime

I've often come across problems where (as a subproblem) I need to decide whether a list of numbers contains only primes or at least one nonprime. Is there an efficient way to do this? Right now I ...
4
votes
1answer
598 views

Intuition and Stumbling blocks in proving the finiteness of WC group

After reading many articles about the Tate-Shafarevich Group ,i understood that "in naive perspective the group is nothing but the measure of the failure of Hasse principle, and coming to its ...
3
votes
1answer
355 views

Subset of natural numbers such that any natural number except 1 can be expressed as sum of two elements

Let $X$ be the set of natural numbers $k_i$, $k_i \geq 1$, with the property that at least one of the equations $p_i = $6$ k_i \pm 1$ gives the $i$-th prime number (disregarding $2$ and $3$), and ...
22
votes
6answers
19k views

Proving Irrationality

How is it possible to prove a number is irrational? First part of that question: How it possible to know that a number will go on infinitely? Second part: How is it possible to know that no ...
2
votes
1answer
120 views

Analytical Reasoning Question III

I tried to solve the number problem below and would like to get input on the final solution I came up with. Thanks in advance! (a) If n is a multiple of 7, how many numbers there that are multiples ...
7
votes
2answers
454 views

Generalization of Bertrand's Postulate

Bertrand's postulate states that there is a prime $p$ between $n$ and $2n-2$ for $n>3$. According to Dirichlet's theorem we have that a sequaence $$a\cdot n+b$$ has infinite primes iff $a$ and $b$ ...
3
votes
1answer
142 views

Why are characters required to be continuous?

I learned from several places that in defining a character of a topological group $G$, we often require it to be continuous, i.e. $\omega:G\to \mathbb{C}^{\times}$ is a continuous group homomorphism. ...
2
votes
1answer
443 views

Proof of max product of partitions of n

For $n \in \mathbb{Z} : n \geq 1$ $ f(n) = \displaystyle\max_{\substack{ x_1+\dotsm+x_k = n\\ x_i\in\mathbb{Z}^{+} }} x_1 x_2 \dotsm x_k $ $$ f(n) = \begin{cases} 1 & \text{if ...
3
votes
1answer
209 views

Counting fractions with $n$ digits in the numerator and denominator

Playing around with fractions, I eventually had to consider the following question: Is there a formula for counting how many proper fractions in lowest terms with $n$ base-$b$ digits in both the ...
10
votes
2answers
518 views

Smallest prime in arithmetic progressions: upper bounds?

This question is inspired by @Dan Brumleve's question on finding Pratt certificates efficiently. In a comment, I say that his problem is as hard as factoring, as long as the following problem is ...
2
votes
4answers
4k views

How can I prove that all rational numbers are either terminally real or repeating real numbers?

I am trying to figure out how to prove that all rational numbers are either terminally real or repeating real numbers, but I am having a great difficulty in doing so. Any help will be greatly ...
6
votes
1answer
288 views

Can a Pratt certificate for a prime be found in polynomial time?

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
6
votes
1answer
335 views

Integral closure of p-adic integers in maximal unramified extension

Let $\mathbb Q_p$ be the field of p-adic numbers, and let $\mathbb Q_p^{\text{unr}}$ be maximal unramified extension in some algebraic closure of $\mathbb Q_p$. My understanding is that $\mathbb ...
3
votes
1answer
185 views

A few questions about $\mathbb{Q}$-models of modular curves (curves given by congruence groups)

I'm just now beginning to learn about descending the curves $X(N)$ to $\mathbb{Q}$, and I have a few questions: Does $X(N)$ have a $\mathbb{Q}$-point for every $N$? What is ...