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)

0
votes
1answer
26 views

Gaps between primes and prime counting function

With two consecutive primes $p_n$ and $ p_{n+1}$ how many solutions does the inequality $$\frac {p_{n+1}-p_n}{2}\ge\pi(p_n) $$ have with $\pi(n) $ being the prime counting function
2
votes
1answer
34 views

Computing periodic continued fractions.

Compute $[1,2,3,\overline{1,4}]$ where $\overline{1,4}$ is the periodic part. I looked into explanations about that, but haven't come by an actual algorithm of computing such a thing. I know it is ...
3
votes
1answer
100 views

A real number is rational $\iff$ its continued fraction expansion is finite.

I know that if this expansion is finite, then I can go to the lowest denominator in the whole fraction and turn it into a fraction and keep doing so until I get a fraction which means the number is ...
2
votes
2answers
47 views

Show that $\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+o(\sqrt{x}) \; (x\to \infty)$

Show that $$\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+o(\sqrt{x}) \; (x\to \infty)$$ I've proven so far that $\sum_{n\le x} \mu ^2(n)=\frac{x}{\zeta(2)}+O(\sqrt{x})$. I want to reduce this error ...
3
votes
2answers
49 views

Let $S(x)=\sum_{p\le x,\; q\le x,\; pq\gt x}\frac{1}{pq}$, where p and q are primes. Find the limit of this function.

Let $$S(x)=\sum_{p\le x,\; q\le x,\; pq\gt x}\frac{1}{pq},$$ where $p$ and $q$ denote prime numbers. Show that as $x\to\infty$,$S(x)$ converges to a constant, and find the value of that constant. ...
1
vote
1answer
77 views

Another question on representation of even integers from some point after , in the form $a^x+b^y$

Does there exist positive integers $x,y$ ; $x>1$ and $k \in \mathbb N$ , such that for every even integer $n \ge k$ , $ \exists a,b \in \mathbb N$ such that $n=a^x+b^y$ , where $a>b>1$ and ...
2
votes
1answer
21 views

Find all the natural numbers which are coprimes to $n$ and are not a fermat witness to compositeness of $n$.

The number $n=35$ is given. Find all the natural numbers $1 \leq a \leq n-1$ which are coprimes to $n$ and are not a fermat witness to compositeness of $n$. Is it enough to say that we are looking ...
0
votes
2answers
23 views

Let $f(n)$ be a function that, given an integer $n$, returns an integer $k$, where $k$ is the [closed]

Let $f(n)$ be a function that, given an integer $n$, returns an integer $k$, where $k$ is the smallest possible integer such that $k!$ is divisible by $n$. Given that $n$ is a multiple of 15, what is ...
3
votes
1answer
42 views

On representation of even integers as $a^x+b^y$

Does there exist some $k \in \mathbb N$ such that for every even integer $n \ge k $ we can find positive integers $a,b,x,y$ such that $n=a^x+b^y$ , where $\gcd (a,b)=1 ; a,b>1$ and at least one of ...
2
votes
0answers
27 views

Approximations of reals by prime ratios [duplicate]

Dirichlet's Approximation Theorem shows how it is possible to find a rational approximation as close as required to any real number. Has it been proved whether there always exists a ratio of two ...
2
votes
0answers
30 views

Finding solutions to a symmetric divisibility condition $x\mid p(y),\;y\mid p(x)$

In general, are there strategies for finding all integers $x$ and $y$ such that $x \mid p(y)$ and $y \mid p(x)$ for some polynomial $p$ with integer coefficients? For example, could we find all ...
0
votes
1answer
93 views

Applications of $p_{n+2}+p_{n+1} \le p_1p_2…p_n , \forall n >2$?

Let $p_n$ denote the $n$-th prime number ; I know that $p_{n+2}+p_{n+1} \le p_1p_2...p_n , \forall n >2$ . I am looking for some applications of it , for example I know one application of it ...
2
votes
5answers
185 views

Finding the numbers that are non-attainable and partitioning.

I have been working through some past math competition problems and have had difficulty in solving some of the ones on number theory. Examples include: 1) If we need 27 cents can we make it using 5 ...
0
votes
0answers
49 views

How can we find the private key?

Alice uses the ElGamal signature scheme with the variables $p=47$, $q=23$ and $g=2$. For two different messages $m_1, m_2$ with $h(m_1)=4, h(m_2)=3$ she produces the signatures $(r_1, s_1)=(14, 8)$ ...
0
votes
1answer
29 views

there exist integer $x,y$ such $p=mx^2+nxy+qy^2$

Assume $\gcd{(m,n,q)}=1$,and $p$ is odd prime number Let $n^2-4mq$ be a quadratic residue modulo $p$ show that: there exist integer $x,y$ such $$p=mx^2+nxy+qy^2$$ maybe this is theorem?
1
vote
1answer
65 views

How many non decreasing sequence of length k is possible?

If we have a set like this { 1A ,2A ,2B, 3A, 3B, 3C}, how many non decreasing sequence is possible, such that number in left is less than number in right of length k? i.e, Length = 2 then the ...
1
vote
0answers
28 views

Simplifying Repeated Summation

Is it possible to simplify the expression below in order to reduce it to a single sum? Would Pascal's Triangle possibly be applicable to finding a solution? $$ \sum_{a_1=1}^n \sum_{a_2=1}^{a_1} ...
1
vote
3answers
124 views

Digit $4896$ of the number$122333444455555666666\ldots$ [closed]

I need find the $4896$th of the number $1223334444555556666667777777\ldots$? I have tried to solve the problem using number bases but I failed
2
votes
1answer
25 views

Blichfeldt-Minkowski Lemma

I'm trying to understand a proof of the following result Theorem: Let $K$ be a number field, and $|| \cdot ||$ the idelic norm (product of the normalized absolute values at each place). There ...
2
votes
1answer
27 views

Solving a linear congruence

Use Euclids algorithm to find the multiplicative inverse of 11 modulo 59 and hence solve the linear congruence: $11x \equiv 8 \mod59$ My working so far.... $ {11v + 51w = 1}$ Using Euclid's ...
9
votes
2answers
72 views

When is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $n,m,j$?

As stated in the title: when is a binomial coefficient a factorial, i.e. when is $\binom{m}{j} = n!$ for some $m,j,n$? I was thinking about this problem a couple of days ago because in all my years of ...
4
votes
1answer
45 views

Prime - composite numbers

Let $n>2$ a natural number. We define the following sets: $$S=\{1 \leq a \leq n : (a,n)=1, a^{n-1} \not\equiv 1\pmod n\} \\ T=\{1 \leq b \leq n : (b,n)=1, b^{n-1} \equiv 1 \pmod n\}$$ Are there ...
1
vote
3answers
53 views

How can we find $m_2$ such that $m \equiv m_1 m_2 \pmod n$ ?

Let $m, m_1 \in (\mathbb{Z}/n\mathbb{Z})^{\times}$. How can we find $m_2$ such that $m \equiv m_1 m_2 \pmod n$ ?? Coud you give me some hints??
2
votes
1answer
56 views

Prove (or provide a counterexample): no pair of primitive Pythagorean triples (a,b,c) and (2a,k,c) exists.

A primitive Pythagorean triple is an ordered set of coprime integers (a,b,c) such that $a^2+b^2=c^2$. Show that the system of Diophantine equations $$a^2+b^2=c^2$$ $$4a^2+k^2=c^2$$ have no solutions.
6
votes
2answers
125 views

Is $y^2=x^3+7$ unsolvable modulo some $n$?

The equation $y^2=4x^3+7$ has no integral solution since $y^2\equiv4x^3+7\pmod4$ has no solution (i.e. has no solution in $\Bbb{Z}/4\Bbb{Z}$). It is well known that $y^2=x^3+7$ has no integral ...
0
votes
1answer
52 views

Ramanujan's proof that Ta(2)=1729 (i.e., that 1729 is the smallest non-trivial taxicab number)

On another thread someone posted a problem from their math homework: to prove that 1729 is the smallest non-trivial taxicab number (or, if you prefer, that $Ta(2)=1729$). Commenters suggested simply ...
1
vote
1answer
16 views

Legendre symbol series

Given an odd prime $p$, prove that $\sum\limits_{x=0}^{p-1}(\frac{x^2-1}{p}) \equiv -1$ $(mod$ $p) $ where $(\frac{a}{p})$ denotes the Legendre symbol. I tried using $(\frac{a}{p}) \equiv ...
0
votes
1answer
18 views

prove or disprove - $p(x)$ = $\sum_0^n$ $a_iX^i$ $c,d,a_i \in $ Z , $n \in N$ then c-d|p(c)-p(d)

Prove or disprove that if $p(x)$ = $\sum \limits _{i=0} ^n a_i X^i$ with $a_i \in \Bbb Z$ and if $c, d \in \Bbb Z$, then $ c-d \space | \space p(c)-p(d)$. What I tried: I know both sums can start ...
3
votes
1answer
72 views

Problem from Olympiad from book Arthur Engel

Each of the numbers $a_1 ,a_2,\dots,a_n$ is $1$ or $−1$, and we have $$S=a_1a_2a_3a_4+a_2a_3a_4a_5 +\dots+ a_na_1a_2a_3=0$$ Prove that $4 \mid n$. If we replace any a i by −a i , then S does not ...
-1
votes
0answers
27 views

congruences in different base

I am new to number theory world. Please help in the following: How to obtain $2^{90} \equiv 64 \pmod {91}$ by repeated squaring to $3^{90} \equiv 1 \pmod {91}?$ Rita darbani
1
vote
0answers
32 views

Easily computable function that is one-to-one and onto with 2 or more inputs

I am looking for a function that will take take n inputs and have 1 output, and knowing the 1 output and function you can get back the n inputs, without error and computationally easy in both ...
-1
votes
0answers
21 views

Calculate the discrete logarithm

Calculate the discrete logarithm of $11$ as for the basis $3$ in the group $(\mathbb{Z}/31\mathbb{Z})^{\times}$, using Pohlig-Hellman. We have to find $0 \leq x \leq 30$ such that $11=3^x$, right?? ...
1
vote
2answers
96 views

solutions to $x^{x+y} = y^4, y^{x+y} = x$ in integers

Three of the elements in the solution set of the simultaneous system $$ x^{x+y} = y^4, \qquad y^{x+y} = x $$ are ordered pairs of integers $(x, y)$. Find these ordered pairs. Substitution leads to ...
3
votes
9answers
70 views

Split $\mathbb{N}$ into a countable union of countable sets. [duplicate]

A friend thought of this problem and I found it interesting to think about so I want to share it with you. I am intrigued how you will solve the problem. Find countably infinite many sets $U_i$ such ...
1
vote
1answer
70 views

What would a base $\pi$ number system look like?

Imagine if we used a base $\pi$ number system, what would it look like? Wouldn't it make certain problems more intuitive (eg: area and volume calculations simpler in some way)? This may seem like a ...
1
vote
2answers
26 views

Quadratic Diophantine Problem in two variables

I have a quick question in regards to solving a quadratic two-variable diophantine problem. The equation is $6x^2 - 2xy + 3y - 17x = 6$. My attempt thus far starts by making y the subject: $$y = ...
1
vote
1answer
53 views

Number of Divisors of N factorial

Say d(N) = Number of factors of N! Briefly: I wish to know if there is a Recurrence relation for this problem Now I wish to Know if there is a way to calculate d(N) in terms of previously calculated ...
2
votes
1answer
82 views

Is $\mathbb{Z}/p^\mathbb{N} \mathbb{Z}$ widely studied, does it have an accepted name/notation, and where can I learn more about it?

Fix a positive integer $p$, possibly prime. For each natural number $n$, there is a ring $\mathbb{Z}/p^n \mathbb{Z}$ together with a distinguished ring homomorphism $$\pi_n:\mathbb{Z} \rightarrow ...
1
vote
2answers
52 views

Why do Smith numbers have to be composite numbers?

As you may know, a Smith number is a number that if all the digits are added together that answer is equal to the sum of its prime factors' digits. Why are 2 and 3 not Smith numbers?
2
votes
1answer
46 views

Why is this a multiple of $s$?

Let $G$ a finite cyclic group of ordern $n=q_1^{a_1} \cdots q_t^{a_t}$, $g\in G$. If $g^{\frac{n}{q_j}}\neq 1$ then $q_j^{a_j}\mid ord(g)$. Proof: Let $s=ord(g)$. Then $s$ is a divisor of $n$, ...
1
vote
0answers
41 views

Fano surfaces all of whose rational points lie on some geometric line

Are there any ? Namely let $X$ be a smooth del Pezzo surface defined over $\mathbb{Q}$ that has rational points and such that the degree of the del Pezzo is small, say $d=3$ or $4$. Is it possible ...
0
votes
0answers
14 views

three questions about syndetic sets

$G$ is a topological group. Definition: A subset $S$ of $G$ is said to be syndetic in $G$ provided that $G=SK$ for some compact subset $K$ of $G$. 1.If $S$ is a syndetic subgroup in $G$, then $G/S$ ...
2
votes
1answer
61 views

Does there exist one number in progression that is coprime to all others? [closed]

Does there exists at least one number in sequence $n,n+1,n+2 ... n+m $ which is coprime to all the others. $n,m$ are positive integers.
1
vote
0answers
25 views

Testing if a number N is prime by its regular polygon's angles

Is it possible to tell if a number N is prime by looking at the angles of a regular N-sided polygon? For example, a regular triangle has 60 degree angles, is there a way to tell that the number 3 is ...
1
vote
1answer
46 views

Find all natural solutions to $x^2+2y^2 = z^2$ [duplicate]

I need to find all natural solutions to $x^2 + 2y^2 = z^2$ What I tried: I did $\pmod 2$ to the equation receiving $z^2 - x^2 \equiv 0 \pmod 2$. Then there are two possibilities: $x^2 \equiv 0 ...
2
votes
1answer
39 views

Solving equations in $\mathbb{Z}_3$ with Hensel's Lemma

Further to the post here, I'm trying to find the $n \in \mathbb{Z}$ such that there is a solution to the equation $$ x^3 +3x+y^3+3y=n$$ in $\mathbb{Z}_3$. Now, I've been able to show that in the ...
0
votes
2answers
83 views

Transcendental numbers & logarithms

Given two coprime positive integers greater than one, say $n,\ m$ , where $n > m$ . How do we find the ratio $\dfrac{\log m}{\log n}$ in terms of $n$ and $m$ symbolically ? Claim: The ratio is ...
0
votes
1answer
33 views

Probable Candidates for the numbers whose sum of divisors is prime?

What are probable candidates for the numbers whose $\sigma(n)$ (sum of divisors) is prime? I know that the list of probable candidates include perfect squares and odd powers of 2 (specifically only ...
1
vote
2answers
54 views

show that $\lim(\pi(x)/x) = 0$

I need to show that: $$\lim_{x\to\infty}(\pi(x)/x) = 0$$ Where $\pi(x)$ is the number of primes smaller then $x$. I tried using the fact that: $$\pi(x)<(1-1/2)(1-1/3)...(1-1/k)X + O(1)$$ but ...
3
votes
2answers
46 views

Proving infintely many primes of the form 6k-1

I have seen the past threads but I think I have another proof, though am not entirely convinced. Suppose there are only finitely many primes $p_1, ..., p_n$ of the form $6k-1$ and then consider the ...