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

Proof about GCD

Prove The GCD of more than two numbers, defined as that positive common divisor which is divisible by every common divisor, exists and can be found in the following way. Let there n numbers $a_1,a_2,.....
1
vote
1answer
40 views

How many polynomials are squarefree?

Of course, this depends on the field, and how we measure "how many," but it seems I cannot find an answer to this except over finite fields. My question specifically is If we have a field $F = \...
1
vote
1answer
107 views

On solving the Collatz conjecture

This method may be kinda inefficient as solving each step may require $O(n!)$ computational time, but for $n$ Collatz operations isn't it possible to disprove the existence of a cycle of $n$ ...
3
votes
2answers
39 views

proof about a lemma of divisibility

Show that if $a|b$ and $b \neq 0$ then $|a| \leq |b|$ Approach: Assume $|a| > |b|$ and $b=ak$ for some integer k $$|a| > |ak|$$ which is a contradiction becasuse $|a||k|=|ak|>|a|$ or $|ak|=...
3
votes
3answers
184 views

Show $GCD(a_1, a_2, a_3, \ldots , a_n)$ is the least positive integer that can be expressed in the form $a_1x_1+a_2x_2+ \ldots +a_nx_n$

Given $a_1, a_2, a_3, \ldots , a_n$ not all zero, show $GCD(a_1, a_2, a_3, \ldots , a_n)$ is the least positive integer that can be expressed in the form $a_1x_1+a_2x_2+ \ldots +a_nx_n$. Also deduce $...
5
votes
1answer
94 views

There are at least two solutions such that $2p_n=p_a+p_b$ ($p$ being prime)

I've stumbled across this playing around and summing primes at random during a boring lecture. Is this a known conjecture? Can it be proven? My conjecture: There exists at least one non trivial ...
12
votes
5answers
442 views

Applications of Character Theory

Some of the applications of character theory are the proofs of Burnside $p^aq^b$ theorem, Frobenius theorem and factorization of the group determinant (the problem which led Frobenius to character ...
2
votes
1answer
44 views

Splitting of a prime and $p$-divisibility on an elliptic curve

Let $K$ be a quadratic imaginary field and let $\lambda$ a prime of norm $l^2$, for a rational prime $l$. We consider $E$ to be an elliptic curve such that $E[p](K)$ is trivial, where $p\neq l$ is a ...
2
votes
2answers
78 views

Find all pairs such that $x^2 y + x + y$ is divisible by $xy^2 + y + 7$

Find all pairs $(x, y)$ of positive integers such that $x^2 y + x + y$ is divisible by $xy^2 + y + 7$. If there are too many to write, write a generic form. I was thinking of rewriting the ...
0
votes
1answer
52 views

How to prove that every natural number not of the form $4^n(8m+7)$ can be written as $x^2 + y^2 + z^2$?

Every natural number not of the form $4^n(8m+7)$ where $m$ and $n$ are natural numbers, can be represented as sum of three squares.
1
vote
1answer
54 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ \frac{x}...
3
votes
2answers
59 views

Origin of Almost Perfect Numbers

Let $N$ be a positive integer. $N$ is called a perfect number if the sum of its positive divisors denoted by $\sigma(N)=2N$. For example $6$ is a perfect number since: $\sigma(N)=1+2+3+6=12=2(6)$. ...
-1
votes
0answers
20 views

Mandelbrot set and times tables

I recently saw a mathologer video on YouTube titled Times tables, Mandelbrot set and the heart of mathematics. It was about generating patterns using tables of numbers. I don't have any idea about it. ...
3
votes
1answer
52 views

Find pairs $(a,b)$ with $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ given

Given a set of GCD's, how to find a set of numbers that satisfy all their criteria? Suppose we are given a $k$ integers $\gcd(a,b),\gcd(a + 1, b),\ldots, \gcd(a + k, b)$ for some k. How to get a and b ...
1
vote
1answer
69 views

Maximal bounds for a variable

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $$1 = px_0+qy_0.$$ Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the ...
17
votes
0answers
217 views
+50

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
5
votes
3answers
60 views

$x^2$ modulo a prime

Prove that $x^2$ modulo a prime $p>2$ takes on exactly $\dfrac{p+1}{2}$ different values. I thought of first saying the residues modulo $p$ can be written as follows: $$0,1,\ldots,\frac{p+1}{2}-1,...
1
vote
1answer
22 views

Endomorphism ring of an abelian variety and its reduction mod $\mathfrak{p}$

Let $A$ be an abelian variety defined over a number field $K$. Let $\mathfrak{p}$ be a prime of $K$ for which $A$ has good reduction and let $k=\mathcal{O}_{K,\mathfrak{p}}/\mathfrak{p}$. Let $\...
4
votes
1answer
42 views

How can I solve $y^4 = 5 \pmod{11\times19}$ with legendre?

Solve $y^4 = 5 \pmod{11\times19}$ I'm trying to let $y^2=A$ then $A^2=5 \pmod{11\times19}$. And solve this problem then $A= 104,-104,28,-28 \pmod{11\times19}$ Then should I solve this problem for ...
0
votes
3answers
101 views

Find all N in $\phi(N)=98$ [on hold]

Solve the equation $\phi(N)=98$ I have no idea how to do it. How to find all N?
1
vote
2answers
27 views

Proof about the quotient remainder theorem by indirect proof

Suppose that every integer can be written in the form $6k+r$ where k is an integer and r is one of the numbers 0,1,2,3,4,5. a) Show that if $p=6k+r$ is a prime different from 2 and 3, then $r=1$ or $...
2
votes
0answers
46 views

Proof about fibonacci numbers by induction

Let $u_1,u_2,....$ be the fibonacci sequence. a) Prove by induction or otherwise thar for n>0, $$u_{n-1}+u_{n-3}+u_{n-5}+...<u_n$$ the sum on the left continuing so long as the subscript remains ...
5
votes
1answer
177 views

Inequality with a rational polynomial

Let $$P(x)=x^{n-1}+a_{n-2}\,x^{n-2}+a_{n-3}\,x^{n-3}+\cdots+a_0\in\mathbb{Q}[x]$$ be a monic rational polynomial of degree $n-1$. I want to show that, for every set of $n$ distinct integers $\{x_1,...
2
votes
1answer
80 views

$\phi(a_1),\phi(a_2),\ldots$ forms an increasing arithmetic sequence?

Let $\phi(m)$ denote the totient of $m$. Does there exist an infinite sequence of positive integers $a_1,a_2,\ldots$ such that $\phi(a_1),\phi(a_2),\ldots$ forms an increasing arithmetic sequence? I ...
0
votes
0answers
15 views

How can I prove this is a reduced residue system?

The problem is [Let m>=3 be a positive integer and let Zm* = {s1,s2,s3...,sφ(m)} denote the standard reduced set of residues modulo m. Derive that s1+s2+...+sφ(m)=φ(m)/2 * m] So I tried to make set T:...
0
votes
1answer
27 views

Well ordering axiom problem

Show that if a and b are positive integers, there is a positive integer n such that $na>b$. Hint: Consider the differences $b-na$, and apply the well ordering axiom. I have no approach yet. My ...
2
votes
2answers
81 views

Find all solutions $10^x=11^y-1$

I tried to solve this like this. $x=1,y=1$ is solution. And Let $x=a y=b\, (a\geq 1,b\geq2)$ Then, $11$ can divide $11^b = 10^a+1$ so $10^a = 10 \pmod{11}$ but order of $11(10) = 2$. Then there ...
3
votes
1answer
94 views

Value group of simple field extension: Are these value groups equal?

Suppose that a field extension $L/K$ is finite, K is a Henselian field with a exponential valuation $v$, and $w$ is an extension of $v$ to $L$. (If it is necessary, we can also assume that $L/K$ is ...
1
vote
0answers
25 views

Explaining a Series Expansion for the Divisor Function

The "sum-of-divisors" function, defined as $\sigma(n)=\sum_{d\,\mid\,n}d$, can be expressed as $$\sigma(n)=\sum_{i=1}^n\sum_{j=1}^i\cos\Big(2\pi n \frac{j}{i}\Big)$$This expansion makes logical sense. ...
7
votes
2answers
181 views

Find number of integral solutions of a*b*c*d = 600

The number of ordered solutions comes out to be 800. I need to find the number of distinct solutions but I'm stuck at calculating the possible combinations. Any ideas on how to proceed further?
3
votes
2answers
46 views

Estimate for $\sum_{q=1}^{M}\frac{\varphi(q)}{q^{2}}$ Related to Bourgain Paper [duplicate]

Let $N\gg 1$ be a large parameter, which I ultimately want to let tend to infinity. I am reading an old paper of Bourgain, where he claims the lower bound (Equation 2.50, pg. 118) $$\sum_{q=1}^{N^{1/...
2
votes
2answers
30 views

Use of greatest common divisor to calculate unknown

We have three numbers $x ,y, z$. If we know the values of $x$ and $z$ then is it correct to say that $y$ should be a multiple of $z/\gcd(z,x)$ for the expression shown below to be true? Here $\gcd$ ...
4
votes
4answers
137 views

Find the highest power of $4$ in $82! + 83!$

I'am only getting $4^{13}$ as answer, but the correct answer is $40$. What am I missing?
0
votes
1answer
92 views

Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the following property

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $1 = px_0+qy_0$. Determine the maximum value of $b-a$, where $a$ and $b$ are positive integers with the ...
3
votes
0answers
62 views

Minimum number of steps to reduce a number to zero.

I am trying to solve a problem which is described below: Given a number n reduce it to 0 in a minimum number of steps using the 2 operations below:1. n can be changed to max(a,b) where n=a*b (a ...
-1
votes
0answers
38 views

irreducibility of monic polynomials over Z [closed]

Statement : Monic polynomials irreducible over Q are irreducible over Z. Where the polynomials belong to Z[x]. How to prove or disprove the statement. It seems like the converse of gauss lemma ...
10
votes
1answer
146 views

When is $\displaystyle\sum_{i=1}^n a_i^{-2}=1$?

For which natural numbers $n$ do there exist $n$ natural numbers $a_i\ (1\le i\le n)$ such that $\displaystyle\sum_{i=1}^n a_i^{-2}=1$? I didn't see an easy way of solving this. There is a solution ...
-1
votes
0answers
14 views

trouble undestanding the proof for the therom “If x is element of N and x != 1, then there is a unique y so that x = y'.”

give the following axioms The following theorem is proven Im having trouble understanding the sentence from "if x=1 then x' element of N ..." up to "and by definition of A, x' element of A." ...
0
votes
2answers
34 views

How can I solve binomial congruent equations?

[Determine whether or not the quadratic congruence $2x^2+5x-9=0\pmod {101}$ is solvable.] I make it to perfect square form and use Legandre symbol. $2(x+77)^2 = 60 \pmod{101}$ Is there any ...
1
vote
1answer
66 views

How can I prove this relation?(Number-Theory)

$\gcd(ord(a),ord(b))=1,\: a^i=b^j \mod n$. Then, $a^i=1 \mod n,\: b^j=1 \mod n$ How can I prove it? This is what I tried. Let $ord(a)=p, ord(b)=q$. Then $a^p=1\mod n,\: b^q=1\mod n$. And $p/\gcd(p,...
1
vote
2answers
47 views

Elliptic curves over $\mathbf{F}_q$ with $q = p^{2m}$

I am reading Washingtons book about elliptic curves and struggling with an exercise there (4.9), which is the following: Let $E$ be an elliptic curve over $\mathbf{F}_q$ with $q = p^{2m}$. Suppose ...
0
votes
1answer
23 views

Maximum length of subset such that all elements are coprime

Given an array, we have to find the length of maximum subset such that all elements of that subset are coprime. That is for $a[i],a[j]$ belonging to subset $\gcd(a[i],a[j]) = 1$ for all distinct $i,j$....
1
vote
1answer
56 views

On the sum of the reciprocals of the zeros of $\zeta(s)$

It is well known that whenever $\rho$ is a nontrivial zero of the Riemann zeta function $\zeta(s)$, then $1-\rho$ is also a zero. But does the equality $\Re \sum_{\rho} \dfrac{1}{\rho} = \Re \sum_{\...
1
vote
2answers
62 views

Non-algebraic structures?

We call group, ring, field,... "algebraic structures". Do we have similar analogue for transcendental numbers? If not, then how do we study interactions between various transcendental numbers? Also, ...
2
votes
1answer
80 views

Are there infinitely many pairs of primes, $p$ and $q$, such that $q = 4p + 1$?

How close can one come to proving that there are infinitely many primes, $p$ and $q$, such that $q = 4p + 1$? The idea for this question came from reading the question and answers posed by user39898,...
3
votes
1answer
27 views

Determine the quadratic character of $293 \bmod 379$.

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
1
vote
0answers
18 views

What are the applications of quantum shuffle multiplication?

I am writing a research paper on quantum shuffle multiplication, and there is just one piece that I'm missing: I want to give one or several examples of its applications, and so far I have not been ...
2
votes
1answer
59 views

Prove that the product is not an integer

Let $p$ be a prime number and $n$ a positive integer. Prove that the product $$N = \frac{1}{p^{n^2}} \prod_{i=1;2 \nmid i}^{2n-1} \left[((p-1)i)! \binom{p^2 i}{pi}\right]$$ Is a positive integer ...