Questions on more advanced topics of number theory. 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
328 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
118 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
193 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 ...
2
votes
2answers
454 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 > ...
21
votes
1answer
754 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
242 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 ...
1
vote
1answer
695 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 ...
12
votes
4answers
1k 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.
7
votes
2answers
272 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
857 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
662 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 ...
3
votes
2answers
364 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
207 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
450 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 ...
8
votes
1answer
460 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
423 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
239 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
1k 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
187 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 ...
27
votes
3answers
535 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
422 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
276 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
241 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
207 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
102 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
533 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 ...
3
votes
1answer
265 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 ...
6
votes
1answer
128 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 $ (..., ...
18
votes
2answers
512 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
423 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 ...
16
votes
8answers
1k 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
651 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})}$$ ...
0
votes
0answers
227 views

N(p) number of solution to x^x =1 (mod p) Miklós Schweitzer 2010

Let $p$ a prime number and $N(p)$ the number of solution to $x^x \equiv 1$ (mod $p$) in $1\leq x \leq p$ . Prove that for sufficiently large $p$ there exist a constant $c < \frac{1}{2}$ such that ...
11
votes
7answers
6k 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
131 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
566 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 ...
4
votes
1answer
352 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 ...
18
votes
6answers
12k 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
113 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
391 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
138 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
357 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
178 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 ...
9
votes
2answers
477 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 ...
1
vote
4answers
2k 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
275 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
294 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
168 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 ...
4
votes
1answer
340 views

Restricted Integer Compositions

Let $c_{k}(N;[a,b])$ denote the number of compositions of $N$ into $k$ parts, where each part is restricted to the interval $[a,b]$, i.e., $N = \sum_{i = 1}^{k} s_{i}$ with $a \leq s_{i} \leq b$. The ...