Tagged Questions

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)

18
votes
2answers
540 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
448 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 ...
19
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
707 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
229 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
7k 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
576 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
353 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 ...
19
votes
6answers
15k 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
407 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
139 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
380 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
187 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
494 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
3k 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
283 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
302 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
172 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
356 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 ...
3
votes
3answers
4k views

How to represent XOR of two decimal Numbers with Arithmetic Operators

Is there any way to represent XOR of two decimal Numbers using Arithmetic Operators (+,-,*,/,%).
2
votes
0answers
79 views

Is it true that $\forall G\leq Aut(\mathbb{P}^1)=PGL_2(\mathbb{C})$ the map $\mathbb{P}^1\rightarrow \mathbb{P}^1/G$ is defined over $\mathbb{Q}$?

Is it true that for every finite $G\leq Aut(\mathbb{P}^1_{\mathbb{C}})=PGL_2(\mathbb{C})$ the morphism $\mathbb{P}^1_{\mathbb{C}}\rightarrow \mathbb{P}^1_{\mathbb{C}}/G$ descends as a morphism (not ...
5
votes
2answers
367 views

How many positive integer solutions to $a^x+b^x+c^x=abc$?

How many positive integer solutions are there to $a^{x}+b^{x}+c^{x}=abc$? (e.g the solution $x=1$, $a=1$, $b=2$, $c=3$). Are there any solutions with $\gcd(a,b,c)=1$? Any solutions to ...
19
votes
0answers
411 views

Dedekind Sum Congruences

For $a,b,c \in \mathbb{N}$, let $a^{\prime} = \gcd(b,c)$, $b^{\prime} = \gcd(a,c)$, $c^{\prime} = \gcd(a,b)$ and $d = a^{\prime} b^{\prime} c^{\prime}$. Define $\mathfrak{S}(a,b,c) = a^{\prime} ...
6
votes
4answers
577 views

Solve $x^3 +1 = 2y^3$

Solve $x^3 +1 = 2y^3$ in integers. (Actually the original question was solve $x^n +1 = 2^{n-2} y^n$ but I can't even solve particular case $n=3$.) Thanks in advance.
0
votes
0answers
120 views

Infinitely many primes beginning with any finite sequence of digits [duplicate]

Possible Duplicate: Proof that there are infinitely many prime numbers starting with a given digit string Given any finite sequence of digits, there are infinitely many primes beginning ...
7
votes
2answers
777 views

Efficient way to find squares mod a prime power?

Assume we are given the problem of say finding all squares modulo $3^4$. Is there any efficient way to compute this without having to check a ton of cases? For just a prime we can use quadratic ...
1
vote
1answer
466 views

Lucas' Theorem and Pascal's Triangle

I have a general question about Lucas' Theorem. Lucas' Theorem says the following: Theorem (Lucas' Theorem) Let $p$ be a prime number. Write $n$ and $k$ in base $p$: $n = a_0 + a_{1}+a_{2}p^{2} + ...
3
votes
2answers
281 views

A sum involving the Möbius function

I am trying to find some work done on the following: $$\sum_{d \vert n}\frac{2^{\omega(d)}}{d}\mu(d)$$ where $\omega(d)$ is the number of distinct prime factors of $d$ and $\mu$ is the Möbius ...
1
vote
2answers
238 views

Consider a sequence of $N$ positive integers with some property

Consider a sequence of $N$ positive integers containing n distinct integers. If $N \geq 2^n$, show that there is a consecutive block of integers whose product is a perfect square. Is this ...
1
vote
3answers
226 views

Product of an even number of consecutive positive integers

Let $z$ be a positive integer. How should one compute all $z$ such that $5^z-1$ can be written as the product of an even number of consecutive positive integers?
4
votes
1answer
759 views

Lucas Theorem but without prime numbers

Let's consider $C(n,k)$ as newton symbol. Lucas Theorem states that $C(n,k)$ is divisable by prime $p$ if and only if at least one of the base $p$ digits of $k$ is greater than the corresponding digit ...
7
votes
4answers
384 views

How to compute that the unit digit of $\frac{(7^{6002} − 1)}{2}$?

The mother problem is: Find the unit digit in LCM of $7^{3001} − 1$ and $7^{3001} + 1$ This problem comes with four options to choose the correct answer from,my approach,as the two number are ...
2
votes
2answers
168 views

If $N= (323232 \cdots 50 \text{ digits})_9$ (i.e in base $9$) then how to find the remainder when this $N$ is divided by $8$?

If $N= (\underbrace{323232 \cdots}_{50 \text{ digits}})_9$ (i.e in base $9$) then how to find the remainder when this $N$ is divided by $8$? I am looking for a "fast" approach that could be ...
1
vote
2answers
269 views

Root of Unity Product

In Washington's Cyclotomic Fields, he makes the following assertion (p. 233): For each positive integer $i$, let $\zeta_i$ be a primitive $i$-th root of unity, chosen such that ...
13
votes
3answers
490 views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what ...
30
votes
2answers
650 views

Proof of no prime-representing polynomial in 2 variables

In "The New Book of Prime Number Records", Ribenboim reviews the known results on the degree and number of variables of prime-representing polynomials (those are polynomials such that the set of ...
3
votes
1answer
711 views

Understanding fibonacci ratio in plants

Recently, a 13year old kid has re-dicovered that there is a magic ratio for branching in plants. Following article describes his work in his own words. ...
1
vote
2answers
89 views

Counting pairs $(a,b)$ with $a^2 +b^2 = t^2$ and $a,b \lt 15$

How many pairs $(a,b)$ are there,such that $a^2 +b^2 = t^2$ where $a,b,t \in \mathbb{N}$ and $a,b \lt 15$? I need a "fast" approach for solving this problem that could be work under a minute.
10
votes
1answer
1k views

After swapping the positions of the hour and the minute hand, when will a clock still give a valid time?

At 12 o'clock, the hour hand and minute hand of the clock can be swapped, and the clock still gives the same time, but at 6 o'clock, it can not be swapped. So in what cases when we swap the hour and ...
7
votes
1answer
248 views

Prime spirals on surfaces of revolution

This is an entirely naive question, and in addition, vague. Apologies in advance! Imagine wrapping the Ulam prime spiral around a surface in $\mathbb{R}^3$, something like this: This suggests ...
2
votes
1answer
85 views

Find the last member remained in game

Imagine a game like this, N man lined in circle, and numbered from 1 to N. Starting from the man with number one, he shout "in", the next one (man number two) shout "out", the next one (man number 3) ...
-39
votes
10answers
3k views

Unique Representation and The Fundamental Theorem of Arithmetic

While reading this thread Is 1 a prime number?, I recalled that The Fundamental Theorem of Arithmetic (FTA) which says that every positive integer greater than 1 can get written uniquely as a product ...
-2
votes
1answer
673 views

Find the sum of digits of a natural number

Teacher asked the students to find the cube root of a natural number but she did not mention the base. Students assumed the base found the cube root. Each student got an integer. Find the sum of ...
0
votes
3answers
200 views

Diophantine equation

If one solves the Diophantine equation $cx + by = a$; i.e., $cx = a - by = a \pmod{b}$ formally, then the answer is $x = (a/c) - (b/c)y$, but the integer character and information is lost and not ...
5
votes
0answers
167 views

Solutions to equation in matrix form

Suppose $x=[x_1, x_2, \cdots, x_n]^t$, $b=[b_1,b_2,\cdots,b_n]^t$ with $b_i\in K$ and $A\in M_n(K)$, where $K$ is a field. There are well known criteria for the system of equations $Ax=b$, by ...
-1
votes
1answer
352 views

Number Theory, Mathematical Fields, and Theoremhood

In classical logic, any given theorem implies any other given theorem (the soundness of classical logic comes as one way to help realize this). I realize the term "mathematics" has a certain ...
1
vote
1answer
191 views

squares ending with repeated digits

I am working on square ending in repeated digits in different bases. I have encountered the following problems during my work. can you generalize the following??? If the digit $a < p$ is a ...
6
votes
2answers
198 views

Numbers p with the property that the sum of the divisors of p (including 1 and p) equals to that of p + 1

So, I wondered if the property described in the title (namely, the property that the sum of the divisors of $n$ equals the sum of the divisors of $n+1$) ever occurred, and went to compute it. Here are ...