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

Divisibility of sums of combinations of integers

I have given a list of $N$ numbers. I want to choose any $M$ of them. I can choose it in ${N \choose M}$ ways. Now I want to determine how many of these chosen groups have a sum, which is divisible by ...
2
votes
1answer
327 views

A convergence problem: splitting a double sum

I have been facing some difficulties with the following question. For an absolutely convergent series $\sum_m a_m$, and the Möbius function $\mu(n)$, $x=(x_1,x_2)\in \mathbb{R}^2$, and $\alpha ...
5
votes
2answers
749 views

Prove $\sum_{d \leq x} \mu(d)\left\lfloor \frac xd \right\rfloor = 1 $

I am trying to show $$\sum_{d \leq x} \mu(d)\left\lfloor \frac{x}{d} \right\rfloor = 1 \;\;\;\; \forall \; x \in \mathbb{R}, \; x \geq 1 $$ I know that the sum over the divisors $d$ of $n$ is zero if ...
0
votes
1answer
75 views

Finding $n$ if the given number is perfect square

Find $n$, if $2^{200}-2^{192} \cdot 31+2^n$ is a perfect square. $$2^{200}-2^{192} \cdot 31+2^n = 2^{192}(2^8-31)+2^n = 2^{192}(256-31)+2^n = 2^{192} \cdot 225+2^n$$ For some $m \in \mathbb{N}$, ...
2
votes
1answer
73 views

Number of solutions mod $p^{2}$

Let $f(n)$ denote a cubic polynomial in $n$ with integer coefficients. Fix a prime $p$. Suppose I know $\#\{a \pmod{p} : f(a) \equiv 0 \pmod{p}\}$. Can one determine $\#\{a \pmod{p^2} : f(a) \equiv 0 ...
2
votes
2answers
151 views

How can there be two products with same remainder when divided with 100

For $a_i,b_j \space \epsilon \space \space \{ 1..100 \} ,\ i \neq j$ ,how can we prove that there exists two products with same remainder $a_i * b_j \space mod \space 100$ . ie $a_1*b_1 mod \ ...
5
votes
1answer
85 views

Non trivial solution over $\mathbb{Z}_p$

Suppose p is an odd prime. Prove that $a_1x_1^2 + a_2x_2^2 + a_3x_3^2 + a_4x_4^2 + a_5x_5^2 = 0$ always have non-trivial solution over $\mathbb{Z}_p$ for any choice of $a_i$ in $\mathbb{Z}$. where ...
16
votes
2answers
741 views

$(x-a)(x-b)(x-c)(x-d)=ex$

We can verify that $x=125,162,343$ are the roots of equation $(x-105)(x-210)(x-315)=2584x$. My question is,Could you find five positive integers $a,b,c,d,e$, which $(x-a)(x-b)(x-c)(x-d)=ex$ has four ...
3
votes
1answer
68 views

Finding solutions set of such equations in $\mathbb Z$, $\mathbb R$ etc

Kindly solve for obtaining solutions of the following equations in $\mathbb Z$, $\mathbb R$ etc 1) Solve in $\mathbb Z$ for $\frac{3}{\sqrt{x}} + \frac{2}{\sqrt{y}} = \frac{1}{\sqrt{2}}$ 2) For M = ...
4
votes
0answers
110 views

How to calculate the sum of floors [duplicate]

The problem is to calculate the value $$ \sum_{i = 1}^{1000} \left\lfloor \frac{1}{\sqrt{i} - \lfloor \sqrt{i} \rfloor} \right\rfloor $$ Where $ i $ is not perfect square number. My thought is, if ...
11
votes
1answer
174 views

Does $n^2+1\nmid n!$ hold for infinitely many $n\in\mathbb N$?

How many positive integers $ n $ satisfy that $ n^2+1 \nmid n! $; are there infinitely many?
4
votes
1answer
80 views

$ n $ lines intersections

As we all know, $ n $ lines which are not coincident may have some intersection points in an Euclid plane. And we define the set of the number of intersection points $ n $ lines can form is $ ...
0
votes
2answers
144 views

Finding the maximum size of a set $Z \subset \mathbb{N}$ s.t. for any $a_1, a_2, a_3 \in Z$, $a_1 + a_2 + a_3$ is prime

What is the maximum cardinality of a set $Z \subset \mathbb{N}$ such that for any distinct $a_1, a_2, a_3 \in Z$, their sum $a_1 + a_2 + a_3$ is prime? This means: $Z = \{a_1, a_2, a_3, \cdots, ...
-1
votes
1answer
75 views

Is any natural number e.g. 0 a count? [closed]

$0$ is a solution to $ax=ay$ for $a$. It is always true that $0x=0y$. Peano's axoim says that $0$ is a natural number, but it doesn't say whether 0 also is a count. $0x$ might not even be an empty ...
6
votes
2answers
478 views

Divisibility - Math Olympiad

Show that for any positive integer $m$, there is an infinite number of pairs of integers $(x,y)$ satisfying the conditions: i) $\gcd(x,y)=1 $; ii) $y \mid x^2+m$; iii) $x \mid y^2+m$.
0
votes
2answers
88 views

Classifying the reals

Can the non-zero real numbers be classified into equivalence classes, where equivalence of $a$ and $b$ means that there is an algebraic expression containing $b$ exactly once that is equal to $a$? For ...
2
votes
1answer
99 views

Converting Prime Numbers from Base $10$ to Base $4$

It seems like when you convert a prime number from base $10$ to base $4$, the base $4$ number, when read back as a base $10$ number is also prime. Example: $13_{10} = 31_{4}$. $31$ in base $10$ ...
5
votes
1answer
228 views

How to find the value of positive integers $a$-through-$h$

If the equation $(x-a)(x-b)(x-c)(x-d)(x-e)(x-f)(x-g) = hx$ has seven positive integer roots, and $a,b,c,d,e,f,g,h$ are positive integers too, how can we find them?
6
votes
0answers
548 views

The prime number theorem and the nth prime

This is a much clearer restatement of an earlier question. In section 1.8 of Hardy & Wright, An Introduction to the Theory of Numbers, it is proved that the function inverse to $ x ⁄ \log⁡ x$ is ...
0
votes
1answer
119 views

real numbers in base 2 - how the infinite series (Σ(b/2^n)) converge to a number in [0,1]?

Any real number in [0,1] has a unique binary decimal representation 0.bbbbb, where each b is either 0 or1. Numerically, o.b_1b_2b_3b_4b_5...=from1 to ∞ Σ(b_n/2^n) (***b_1=b-sub-one) where the ...
6
votes
3answers
224 views

Find the smallest integer $n > 0$ such that $2012$ divides $9^n-1$.

Find the smallest integer $n > 0$ such that $2012$ divides $9^n-1$. my thoughts: $$2012=2 \cdot 2 \cdot 503$$ $503$ is prime. so by fermats little theorem $9^{502} \equiv 1$(mod $503$). again ...
3
votes
1answer
101 views

Imperfect digit-to-digit invariants in Base $10$

$3435 = 3^3 + 4^4 + 3^3 + 5^5$ is an example of a perfect digit-to-digit invariant. Fact: The number of PDDIs is finite for any given base; in particular, for base $10$. Question: Working over base ...
10
votes
2answers
776 views

Solve $y^2= x^3 − 33$ in integers

This is not homework, could someone provide a nice clear proof as I have been struggling with this for some time. Solve the equation $y^2= x^3 − 33$; $x, y \in \mathbb{Z}$
32
votes
2answers
486 views

Are there/Why aren't there any simple groups with orders like this?

The orders of the simple groups (ignoring the matrix groups for which the problem is solved) all seem to be a lot like this: ...
11
votes
1answer
351 views

Math Olympiad - pre-periodic function

Let $c \in \mathbb{Q}$, $f(x)=x^2+c$. Define $$f^{0}(x)=x, \ \ f^{n+1}(x)=f(f^{n}(x)), \ \forall n \in \mathbb{N}$$ We say that $x \in \mathbb{R}$ is pre-periodic if $\{f^{n}(x), n \in \mathbb{N}\}$ ...
3
votes
1answer
136 views

quadratic extension of $\mathbb{Q}(X)$ generated by the square root of a square-free polynomial

Let $f(X)\in\mathbb{Q}[X]$ be a square-free polynomial, that is, not divisible by any prime of $\mathbb{Q}[X]$. Let $K:=\mathbb{Q}(X)[Y]$, where $Y$ is a square root of $f(X)$, or equivalently $Y$ ...
1
vote
1answer
105 views

Unramification and compositum

The background is: a field $K$ complete with respect to a discrete valuation $|\ |$. We write $A$ and $k$ for his discret valuation ring and the residue field of $A$. We assume that $K$ and $k$ are ...
2
votes
5answers
205 views

On prime numbers

let $q$ be a prime let $p = 2^q -1 $ is p must be prime always for any prime q ? is this is true always ? or it is false for some prime q ? if it is false , give an example to show that there ...
12
votes
1answer
273 views

primes represented integrally by a homogeneous cubic form

Expired by this question Show determinant of matrix is non-zero I am moved to ask: Given integers $a,b,c,$ and cubic form $$ f(a,b,c) = a^3+2 b^3-6 a b c+4 c^3 = \left|\begin{bmatrix} a & 2c ...
8
votes
2answers
307 views

Diophantine Quintuple?

I have come across the following set of numbers: $\{1, 3, 8, 120\}$ These are positive integers where the product of any two of the numbers equal to a number that is one less than a square number. ...
4
votes
1answer
101 views

quadratic extension of $\mathbb{Q}(X)$

Consider the ring $\mathbb{Q}[X]$ of polynomials in $X$ with coefficients in the field of rational numbers. Consider the quotient field $\mathbb{Q}(X)$ and let $K$ be the quadratic extension of ...
4
votes
2answers
238 views

Rational approximations to $\sqrt 2$

I find this problem is very interesting, but now I can't solve it. Given $n$ a positive integer, let $$f(n)=\min_{m\in\Bbb Z}{\left\lvert\sqrt{2}-\dfrac{m}{n}\right\rvert}.$$ If there is a sequence ...
3
votes
5answers
992 views

How to create a generating function / closed form from this recurrence?

Let $f_n$ = $f_{n-1} + n + 6$ where $f_0 = 0$. I know $f_n = \frac{n^2+13n}{2}$ but I want to pretend I don't know this. How do I correctly turn this into a generating function / derive the closed ...
2
votes
2answers
112 views

Solve for system of diophantine equations

$\cases{x+1=a^2 \cr x^3-x^2+1=b^2}$ I just can found a trivial solution $x=0$. Is there any other ?
1
vote
6answers
563 views

power set of natural numbers equal to the power set of integers

I need show that the two given sets: power set of natural numbers and power set of integers, have equal cardinality by describing a bijection from one to the other (describe the bijection with ...
1
vote
2answers
62 views

How to find $a,b\in\mathbb{N}$ such that $c = \frac{(a+b)(a+b+1)}{2} + b$ for a given $c\in\mathbb{N}$

Suppsoe that $$c = \frac{(a+b)(a+b+1)}{2} + b$$ Now $c$ is given - how does one find satisfying $a, b$?
7
votes
1answer
448 views

Prime number generating function as product expansion

I am interested in prime number generating function. $$f(x)=1+\sum \limits_{k=1}^\infty p_{k}x^k=1+2x+3x^2+5x^3+7x^4+11x^5+....$$ I would like to find the function as product expansion and to check ...
0
votes
2answers
28 views

For what range does this floor function scale to?

I have $\lfloor\frac{X}{(2y+1)^2}\rfloor = k$ where $X$ and $k$ are known. For what values of $y$ will this hold true? edit: all are positive integers
3
votes
1answer
50 views

Representing an element mod $n$ as a product of two primes

Given a positive integer $n$ and $x \in (\mathbb{Z}/n\mathbb{Z})^*$ what is the most efficient way to find primes $q_1,q_2$ st $$q_1q_2 \equiv x \bmod n$$ when $n$ is large? One option is just to ...
1
vote
1answer
165 views

Are there any errors in my proof that only perfect squares have rational square roots?

This is a very simple proof, but I know that proofs which are this simple can often have some erroneous assumptions. Is mine okay? Argument: With the exception of perfect squares, there are no ...
0
votes
2answers
219 views

Solve for diophantine equation $x^n + y^n + z^n =1$ [closed]

Solve for diophantine equation $x^n + y^n + z^n =1$ $x^n+y^n+z^n=2$ Is this equation solve-able ?
11
votes
3answers
355 views

Problem with infinite product using iterating of a function: $ \exp(x) = x \cdot f^{\circ 1}(x)\cdot f^{\circ 2}(x) \cdot \ldots $

[update]: I made the question more precise, more general and added a follow up question Considering the iteration of functions (with focus on the iterated exponentiation) I'm looking, ...
1
vote
2answers
155 views

Congruence equation mod $p$ involving the multiplicative order

Say $p$ is an odd prime s.t $p$ doesn't divide $x$. Let $x$ belong to the exponent $n$ modulo $p$. I need to show that if $n>1$, then $x + x^2 + ... + x^{n-1} ≡ -1 \mod p$ I'm not sure how to go ...
2
votes
3answers
2k views

How to find all the primitive roots in $\mathbb{Z}/49\mathbb{Z}$.

I need to find all the primitive roots of 49. First note, $ ϕ(49) = 42 $ Is there an easier way to go about trying all numbers less than $42$ to find the primitive roots of $49$ if we already know ...
1
vote
4answers
77 views

Simple Modulo Questions

Hey guys I have some questions regarding modulo. Some of these are solvable and some are not but I have to prove why they have no solution. Any help would be appreciated thanks! $39x\equiv65 \pmod ...
1
vote
1answer
76 views

Something like an incomplete gamma function

I want to compute $\int_0^z t^{-b}e^t \,dt$ where $b>0$ by using incomplete gamma function. Can I rewrite my integral as a form of the incomplete gamma function?
9
votes
3answers
673 views

A cohomological statement equivalent to the Riemann Hypothesis

Is there a possibility for looking for a theory of cohomology and an equivalent cohomological statement for Riemann hypothesis over $\mathbb{Z}$?
1
vote
1answer
159 views

Dilogarithm Identities

Is there a cleaner way to write: $$ f(x) = \operatorname{Li}_2(i x) - \operatorname{Li}_2(-i x) $$ in terms of simpler functions? I don't know enough about dilogarithms, and the basic identities I see ...
1
vote
0answers
55 views

Embedding an $n$-simplex in $\mathbb{Z}^n$.

I am trying to understand the proof of embedding an $n$-simplex in $\mathbb{Z}^n$ for specific values of $n$. The proof can be found here. I am stuck on what is meant by "the reflection with axis ...
2
votes
0answers
67 views

If $x \sim U(Z_n^*)$ then $x^2 \pmod n\sim U(QR_n)$?

Define: $Z_n^*=\{x \in Z_n | \operatorname{gcd}(x,n)=1\}$ $QR_n=\{x \in Z_n | \exists r \in Z_n \; s.t. \; r^2 =x\}$ How can I show that $x \sim U(Z_n^*) \implies x^2 \pmod n \sim U(QR_n)$? Thank ...