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

Algorithms for finding the multiplicative order of an element in a group of integers mod m

What are some algorithms for finding the multiplicative order of an element in a group of integers mod m, besides the naive one?
0
votes
0answers
24 views

Name for “relative difference”

If we want to express that two numbers $x, y$ are not so far away from each other absolutely we use the absolute value function $|\cdot|$ with $0 < \epsilon \ll 1$: $$|x-y| < \epsilon$$ ...
0
votes
1answer
36 views

An integer equation

I need to prove the following interesting result: given $a,c,d\in \mathbb{N}^{+}$, where $a\nmid c$ and $c\neq d$, then the following statement is not true: for any $k_1,k_2\in \mathbb{N}^{+}$ there ...
0
votes
1answer
67 views

Finitely Many Prime Tuples can get a Factorial

Let $k$ and $a_1,a_2 \cdots a_k$ be fixed integers, each of them being $>1$. Show that there are only finitely many $k$-tuples of primes $(p_1,p_2, \cdots p_k)$, with the following property: there ...
1
vote
0answers
65 views

number set with non-adjacent digits

I'm not sure such thing exists, or even if I'm asking for a valid thing, but I'll do my best describing it. At least the thing I want is similar to Gray code, so should be valid. So, I want to know ...
13
votes
1answer
652 views

Big-Daddy-Conjectures and Hierarchy of Mathematical Conjectures

I am interested in the Hierarchy and Connections between various different open problems in Mathematics, and the most general conjectures in various fields of Mathematics. Examples of Hierachy ...
0
votes
3answers
49 views

A pretty much simple number theory problem

Let $x$ be an irrational number, and $n$ be a positive integer. Will there ever be a set of $(n,x)$ which satisfies $x(n-x) \in \mathbb{Z}$ ? If so, could you suggest those numbers? And, if not, ...
1
vote
0answers
33 views

Maximal number of inequivalent elements in $\mathbb{E}_p$

For a prime $p$ of the form $12k+1$ and $\mathbb{Z}_p=\{0,1,2,\cdots,p-1\}$, let $$ \displaystyle \mathbb{E}_p=\{(a,b) \mid a,b \in \mathbb{Z}_p,\quad p\nmid 4a^3+27b^2\}$$ For $(a,b), (a',b') \in \...
5
votes
2answers
227 views

The prime elements of the ring $ \mathbb{Z} \! \left[ \dfrac{i \sqrt{3} - 1}{2} \right] $.

I have to study the prime elements of the ring $ \mathbb{Z} \! \left[ \dfrac{i \sqrt{3} - 1}{2} \right] $. For the moment, I cannot find the general form of such elements. Can you help me? Thanks! :)
1
vote
1answer
105 views

If p and q are distinct prime numbers, it is true that we always have $p^{q-1}+q^{p-1} \equiv 1 \mod pq$?

If p and q are distinct prime numbers, it is true that we always have $p^{q-1}+q^{p-1} \equiv 1 \mod pq$? More generally if $m,n \in \mathbb{N}$ are relatively prime, is it true that $n^{\phi(m)}+m^{\...
0
votes
1answer
87 views

Even Odd counting

Given an integer $Q$ and an array $A$ of size $N$, can we figure out the answer to each of the $Q$ queries? Each query contains two integers $x$ and $y$, and we need to find whether the value $\...
6
votes
3answers
121 views

Proving $n^2(n^2+16)$ is divisible by 720

Given that $n+1$ and $n-1$ are prime, we need to show that $n^2(n^2+16)$ is divisible by 720 for $n>6$. My attempt: We know that neither $n-1$ nor $n+1$ is divisible by $2$ or by $3$, therefore $...
2
votes
0answers
127 views

Find all pair(s) of positive integer $(a,b)$ such that $\frac{a^2}{2ab^2 -b^3+1}$ is also positive integer too?

Another number theory problem. I can find the small value of $b$ such that 0,1,2. But, I cannot find the upper limit of $b$, such that the value of $b$ is limited. How can I find the solution $(a,...
2
votes
0answers
82 views

A better Reference than Andre Weil's Basic Number Theory

I want to get a feel for Adeles. I have been suggested to read the first 4 chapters of Andre Weil's Basic Number Theory. I am very confused by the writing style and conventions (like a field need not ...
0
votes
1answer
49 views

Polynomial Diophantine Equations

So in general how does one decide if: $$ a_0 + a_1x + a_2x^2 ... a_{n_1}x^{n_1} = b_1y + b_2y^2 ... + b_{n_2}y^{n_k}$$ Has solutions for integers $x,y$ given real numbers $a_0, a_1. .. a_{n_1}, b_1 , ...
0
votes
2answers
46 views

Can someone explain this exponent simplication ? $a^4 \equiv a^{2014} \pmod{31}$

I was reading this answer and I am not sure I get how $a^4$ got introduced here: Hence, $a^4 \equiv a^{2014} \equiv −1 \pmod{31}$. Can anyone explain that simplification? Thanks!
1
vote
1answer
32 views

To find solutions of $\dfrac n{d(n)}=p$

For positive integer $n$ let $d(n)$ denote the no, of positive divisors of $n$ , then for a prime $p$ , how do we find all solutions of $ \dfrac n{d(n)}=p$ ?
0
votes
1answer
122 views

Integer solution of $x^5+31=y^2$ [closed]

Does the equation $x^5+31=y^2$ has no solution in integers $x,y$ ?
2
votes
1answer
120 views

$p$-adic expansion

I have just touched on this topic, please guide me along. If I have a prime number $p=10^{10}+19$, and a $p$-adic number $\alpha=\frac{16}{17}$. How do I derive its $p$-adic expansion? Thanks in ...
0
votes
2answers
34 views

Prove that for the primitive root $[g]$ modulo p we have $[g]^m=[g]^n \iff p-1\mid m-n$

Prove that for the primitive root $[g]$ modulo $p$ we have $[g]^m=[g]^n \iff p-1\mid m-n$. Proof: We know If $g$ is a primitive $p$-root of unity, then $g^n\equiv 1 \pmod p \iff (p-1)\mid n$. Hence ...
1
vote
1answer
31 views

If $(\frac{Q}{P})=1$, then the congruence above doesn't have a solution.

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \pmod P$. What is an example that shows that If $(\frac{Q}{P})=1$, then the congruence ...
-1
votes
2answers
248 views

Let p be an odd prime and let g be a primitive root modulo p.

Let p be an odd prime and let g be a primitive root modulo p. Prove that $g^k$ is a quadratic residue modulo p if and only if k is even. Use (a) to give a quick proof that the product of two ...
3
votes
1answer
76 views

Liouville number + rational number

The set of Liouville numbers is defined as all irrational $x$ such that for each natural $n$ there exists integers $p$ and $q > 1$ such that $|x - p/q| < 1 / (q^n)$. QUESTION: Is a Liouville ...
4
votes
3answers
112 views

Find all positive integer solutions $(x,y,z)$ that satisfy $5^x \cdot 7^y +4= 3^z$?

This is another contest math-problem. The only problem that I cannot find the way to tackle this problem. Can anybody try to provide the solution to solve this problem? Thanks
5
votes
4answers
159 views

Integer solutions to $a^{2014} +2015\cdot b! = 2014^{2015}$

How many solutions are there for $a^{2014} +2015\cdot b! = 2014^{2015}$, with $a,b$ positive integers? This is another contest problem that I got from my friend. Can anybody help me find the ...
3
votes
1answer
208 views

The most efficient method for generating new prime numbers

What is the most efficient method for generating a prime number larger than the largest known prime number, and what is the complexity of this method? Techniques considered: Mills' Constant - ...
0
votes
1answer
26 views

Solve $2\tau(n^2)=3\tau(n)$ in the set of naturals

$\tau(n)$ is the number of divisors of $n$. My idea was that I need to approximate the growth of $\tau$ and then find $n_0$ after which all $\tau(n^2)$ are greater than $\frac{3}{2}\tau(n)$. I assume ...
1
vote
0answers
37 views

Determining the number of solutions of the equation $y^2 = x^3 + x^2 + 5$ in $\mathbb{Z}/p^k \mathbb{Z}$ in function of $k$.

I found a question that asked me to discuss the number of solutions of the equation $y^2 = x^3 + x^2 + 5$ in $\mathbb{Z}/p^k \mathbb{Z}$ in function of $k$. I would like to use the multivariate ...
0
votes
1answer
121 views

How prove this diophantine equation $3^x-2^y=k$ have finitely many integral solutions

For any $\forall k\in N^{+}$ show that the diophantine equation $3^x-2^y=k$ have finitely many integral solutions. My try: if $k=2m$,then $$3^x=2^y+k=2^y+2m$$ It is clear there is no integer ...
1
vote
2answers
88 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
0
votes
1answer
167 views

References for Legendre's prime-counting function

This question is about Legendre's prime-counting function, the one that can be used to calculate the exact amount of prime numbers that are less than or equal to a given number (as long as the number ...
0
votes
1answer
54 views

What are the smallest numbers $n$ such that $\dfrac{d(n)}{\ln(n)} \geq k$ where $d(n) = \sigma_0(n)$ is the number-of-divisors function?

I have calculated $\dfrac{d(n)}{\ln(n)}$ on a few highly composite numbers up to 5040. Here is what I got: $\dfrac{d(120)}{\ln(120)} = 3.3420423$ $\dfrac{d(360)}{\ln(360)} = 4.0773999$ $\dfrac{d(...
2
votes
0answers
48 views

Classification of quadrtic forms over Q_p

I need some one to recap the topic with me and correct me when i am wrong. There are basically just a few questions at the end,but its important to also show what i know and not just what i dont. ...
3
votes
2answers
142 views

arithmetic sequence $8n+1$ and the collatz conjecture

Is it a known result that if for all $n$ the collatz sequence of $8n+1$ lead to $1$, all natural numbers will?
13
votes
2answers
492 views

least common multiple $\lim\sqrt[n]{[1,2,\dotsc,n]}=e$

The least common multiple of $1,2,\dotsc,n$ is $[1,2,\dotsc,n]$, then $$\lim_{n\to\infty}\sqrt[n]{[1,2,\dotsc,n]}=e$$ we can show this by prime number theorem, but I don't know how to start I ...
1
vote
0answers
25 views

Finding coefficients of the min polynomial of an $n\times n$

Given an $n\times n$ matrix, for ease assume this matrix is over the $F_m$. What we know about min poly is the the non-zero components of the min polynomial for this case, ie if there is $x^2$, or $x^...
4
votes
1answer
113 views

Square free integers

Let $Q(n)$ denote the number of square free integers $\le n$. It is easy to show that $$Q(n)=\frac{6}{\pi^2}n+O(n^{1/2})$$ However Wikipedia also tells me that $$Q(n)=\frac{6}{\pi^2}n+O(n^{1/2-\...
0
votes
1answer
230 views

Modulation and translation properties of DFT

Consider the discrete fourier transform over a finite field $GF(q)$. Let also $\omega$$\in$$GF(q)$ be an element of order $n$ and which is an $n$-th root of unity. Definition 1. Let $v$ = ($v_0$, $...
3
votes
1answer
32 views

Find all $n$ so that $c_n$ $>$ $\pi(n^2)$

Find all $n$ $\in$ $\mathbb{N}$ so that $p_{c_n}$ $>$ $n^2$ where $p_n$ denotes the $n$-th prime and $c_n$, the $n$-th composite. I have tried doing the problem using The stronger version of ...
0
votes
0answers
44 views

the non-zero integer roots of an inequality

Let $a,b,c,d$ be real numbers, and $ad-bc \ne 0$, given $$|(ax+by)(cx+dy)|\le \frac{1}{2}|ad-bc|.$$ does there exist non-zero integers $x,y$ which satisfy the above inequality ?
4
votes
1answer
388 views

Finding a rational number which is simply normal to relatively prime bases

Let $n\ge 2\in\mathbb Z$. Suppose that a base-$n$-decimal $(0.a_1a_2a_3\cdots)_n$ represents $\sum_{k=1}^{\infty}\frac{a_k}{n^k}$ where $a_{i}\in\{0,1,\cdots,n-1\}\ (i=1,2,\cdots)$ is each digit ...
0
votes
3answers
51 views

How many are possibilities to build count $n$ summing $k$ other counts?

I have got an integer $n$. I have to build it by summing $k$, not necessary, different integers. Is there any overall formula to count how many are possibilities to build count $n$ summing $k$ other ...
2
votes
0answers
38 views

binomial coefficents and composite numbers

Given a binomial coefficient $${n \choose k}$$ With $n>3$ and $k\neq 1$ or $n-1$, is the binomial cofficient always a composite number?
1
vote
4answers
41 views

Where's my error on finding all the solutions of a linear congruence?

I'm supposed to find all solutions of each of the linear congruence. 9x ≡ 5 (mod 25) I know there are other posts on the site about this, but I don't really follow. Here's what I did: I used ...
0
votes
1answer
82 views

Pythagorean triple $(\xi,n,\zeta)$,prove that at least one of the numbers are divisible by $3,5$ [duplicate]

Let a Pythagorean triple $(\xi,n,\zeta)$.Prove that at least one of $\xi,n$ is divided by $3$ and that at least one of $\xi,n, \zeta$ is divided by $5$. That's what I have thought: We suppose that : ...
1
vote
1answer
31 views

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \mod P$. Prove that

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \mod P$. Prove that If the equation has a solution, then $(\frac{Q}{P})=1$ That the coverse ...
0
votes
0answers
28 views

Diophantine equations,is that what I have done right?

I have solved the following diophantine equations: $14x+35y=93$ $56x+72y=40$ That's what I have tried: $gcd(35,14)=7$ , but $7 \nmid 93,$ so the first diophantine equation has no solution. $gcd(...
2
votes
1answer
22 views

Show that the statement in the Law of Quadratic Reciprocity can be written (as Gauss did as)

Show that the statement in the Law of Quadratic Reciprocity can be written (as Gauss did as) $(\frac{p}{q})=(\frac{q \times (-1)^\frac{q-1}{2}}{p})$. One is this question correct? Second if it is ...
0
votes
2answers
76 views

Can the Losanitsch triangle be derived from the Pascal's triangle?

Assuming of course that the Losanich triangle is a real thing. I saw it on Wikipedia and you know how people put fake stuff on their sometimes, so let me know if its fake.
3
votes
2answers
721 views

The sum of $n$ consecutive Fibonacci numbers.

The sum of $8$ consecutive Fibonacci numbers is divisible by $3$. How can I generalize this for the sum of $n$ consecutive Fibonacci numbers? For example, $$1+1+2+3+5+8+13+21=54=3\times 18 \\ ...