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
2answers
39 views

divisibility of complex numbers

I want to show that $(a + bi)|(c + di)$ is equivalent to the statement that the ordinary integers $(a^2 + b^2)|(ac + bd)$ and $(a^2 + b^2)|(-ad + bc)$. I also want to show that $(a + bi)|(c + di) ...
2
votes
2answers
32 views

Number Theory Simple Proof

I am looking at a solution for a problem where the following line is stated but not explained, and I can not seem to make sense of it: If a prime $p\equiv 3\pmod 4$ then why is $\frac{p(p+1)}{2}$ ...
1
vote
0answers
14 views

Solving quadratic congruences?

I am having trouble learning to solve quadratic congruences. I need to solve $$ x^2=317\pmod{ 77747} $$ using two different methods. Setting up in an index table isn't feasible since $p$ is so ...
3
votes
1answer
37 views

How to decide which moduli to check when solving a “polynomial” congruence?

Consider the following problem: Find all integer solutions to $y^2 = x^5 - 4$. The solution goes something like – check modulo 11, where $x^5 \equiv 0, \pm 1$, and then check cases to arrive at ...
4
votes
2answers
311 views

Is this a meaningful approach to primes?

Motivation: I tend to be good at recognising patterns and I saw one with factorial: $$ n! = \prod_{i=1} p_i^{J(n,p_i)} $$ where $p_i$ is the $i$'th prime and $$ J(n,i)= \sum_{S=1}^\infty [n/i^S] $$ ...
1
vote
1answer
57 views

Solving a Diophantine equation: $y^x=x^{2007}$, $x$ and $y$ integers.

I found this Diophantine equation and to solve it I used the definition of logarithm but the solution doesn't require the use of logarithmic rules. I solved it in this way: $$y^x=x^{2007}$$ ...
0
votes
1answer
24 views

Primitive root problem

Let $p>3$ be prime number and $a$ primitive root modulo $p^2$. Prove that $x^{p-1}\equiv 1 \pmod{p^2}$ solutions are $\overline{a}^p,\overline{a}^{2p},\ldots ,\overline{a}^{(p-1)p}$. Any ideas on ...
3
votes
1answer
56 views

How to define multiplication in $\mathbb{Z}$ with divisibility and addition?

Q: Show that $(\mathbb{Z},|,+,0,1)$ defines multiplication in $\mathbb{Z}$. I know how to do this in $\mathbb{N}$, but I'm stuck trying to do this is $\mathbb{Z}$. The idea I have is to define lowest ...
1
vote
1answer
44 views

the blood test riddle (number theory)

A microbiologist has been given a set of $100$ blood vials. Exact one of those $100$ vials is positive to a concrete disease X. The microbiologist desires to send only $7$ vials for analysis. He can ...
1
vote
0answers
24 views

Is the discriminant of a polynomial surjective onto $\mathbb Z$?

Consider polynomials of degree two over $\mathbb Z$: $f = ax^2+bx+c$ The discriminant is $D = b^2-4ac$ And we can show that $D=2$ is not a possible value for $D$. I wonder if the value $D=2$ ...
0
votes
2answers
32 views

Standard result for $\log(x)$

$$\sum_{1\leq m\leq x/d}\frac{1}{m}=\log(\frac{x}{d})+O(1)$$ I read this result in lecture papers I was going through and can't find anything about its origin. Is there a standard summation result ...
2
votes
0answers
8 views

Town Network - Show there is a Tetrahedron of the Same Transport

Question: There are 18 towns such that between each pair of towns there is either a train or bus service (not both). Prove that there are 4 towns such that all 6 of their pairwise connections use the ...
3
votes
1answer
45 views

Runs of consecutive numbers all of which are rebel numbers

A positive integer is said to be a rebel number if it is the product of numbers none of which share any of the original number´s digits. Thus 10 = 2 x 5 is a rebel number, while none of the primes is. ...
1
vote
3answers
28 views

Divisibility of integers by integers

We are given a number $$K(n) = (n+3) (n^2 + 6n + 8)$$ defined for integers n. The options suggest that the number K(n) should either always be divisible by 4, 5 or 6. Factorizing the second bracket ...
0
votes
1answer
21 views

Arithmetic functions proof

Theorem: Let $f$ be an arithmetic function such that $f(1)=1$. Then there exists a unique arithmetic function $g$ such that $f\ast g =\epsilon$. The arithmetic function $g$ is called the Dirichlet ...
0
votes
2answers
23 views

Mistake in proof of sum of divisors function $\sigma(n)$

The proof derives the correct result, but I cannot see how the first equality is correct. To begin we use the formula $\sigma(n)=\sum_{d\mid n}d$ This is the first step in the proof: $$\sum_{1\leq ...
1
vote
0answers
5 views

Is every Pisot-like integer the product of a Pisot integer and a root of unity?

For lack of better terminology, let's call an algebraic number $\beta$ Pisot-like if $|\beta| > 1$ and all its conjugates lie inside the complex unit circle (here $|\cdot|$ is the usual absolute ...
1
vote
0answers
14 views

Prove that the “additive” operation of the module($\mathbb{Z}_{p}^{*},\mathbb{Z}_{p-1},\cdot$) is continuous.

Consider the following module $\mathcal{M}=$($\mathbb{Z}_{p}^{*},\mathbb{Z}_{p-1},\cdot$) in which the "additive" operation is defined by normal multiplication in $\mathbb{Z}_{p}^{*}$ and scalar ...
2
votes
1answer
20 views

How does $ \text{Gal}(K / k) $ act on ideles?

Let $K/k$ be cyclic of degree $N$, Galois group $G$. I want to define some action of $G$ on the group of ideles $J_K$ which commutes with multiplication. A natural way to do this is to take each ...
-4
votes
0answers
29 views

Finding the modulo of 801 [on hold]

If $d_{k}(m)$ is the number of divisor of m that are congruent to $k$ modulo $4$. How can I find $d_{1}(801)$ and $d_{3}(801)$ .
0
votes
1answer
20 views

Sum-of-divisors determinant

Let $\sigma_k(n)=\sum_{d|n}d^k$ be the generalized sum-of-divisors function. Let $S_n$ be the matrix defined by $[S_n]_{ij}=\sigma_i(j)$. I read a comment somewhere that $$\det(S_n)=1!\cdot 2!\cdots ...
1
vote
3answers
38 views

Divergence of sum reciprocal of primes using Bertrand's Postulate

I have been trying to prove that the series of reciprocal of primes diverges by only using Bertrand's Postulate. Does anybody know if this is possible? Or is it the case that this postulate is not ...
1
vote
2answers
19 views

base b expansion of real numbers

This is a problem in Zygmund's analysis book. It is intuitively very straightforward. However, I could not give a rigorous proof. I hope someone can show me how to prove this rigorously. Problem: ...
0
votes
1answer
35 views

The genus of a certain kind of cubic

I have a cubic curve that looks like $$ a_0 x^3 + a_1 x^2 y + a_2 xy^2 + a_3 y^3 = b $$ with $a_0, a_1, a_2, a_3$, and $b$ all integers, and $a_0$ and $b$ nonzero. I'm not sure but I think in my ...
2
votes
2answers
53 views

Compute the values of two infinite products whose factors are the same

I have the following question: How to prove that $(1-\frac{1}{2})\cdot (1+\frac{1}{3})\cdot (1-\frac{1}{4})\cdot (1+\frac{1}{5})\cdot (1-\frac{1}{6})\cdot (1+\frac{1}{7})\cdot ...
0
votes
1answer
21 views

Solving an equation with complex numbers

I want to use complex numbers to solve the following problem: $x^2 = 95 - 168i$. I am sure there are a few ways of doing this but the way I want to do it is to let $x = a + bi$ and then solve for $a$ ...
3
votes
1answer
30 views

Is there any solution to this quadratic Diophantine 3 variables equation?

Is it possible to find all positive integer triplets $(x,y,z)$ satisfying the parametric equation : $$x^2 + 2ax + y^2 + 2by = z^2 + 2cz$$ Here $a, b, c$ are fixed positive integers.
0
votes
0answers
15 views

Decryption of RSA

I am given the following information about an RSA-encryption: $e=31671865305320609$ (public key) and $n=10e+3$. Then I am given the ciphertext $c$ which I omit here due to his length. The task is to ...
7
votes
1answer
64 views

If all the numbers $(1^\alpha,\,2^\alpha,\,3^\alpha,\,\dotsc)$ are integer, then $\alpha$ is an integer.

A theorem of Siegel asserts that If $\beta>0$ and $2^\beta,\,3^\beta,\,5^\beta$ are integers, then $\beta$ is an integer. The following result is a beautiful consequence of this theorem ...
1
vote
2answers
26 views

Show $\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$

I have been trying to get my head around this step in a proof, but havn't been able to, Question: Show $$\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$$ ...
2
votes
2answers
270 views

Fermat’s Little Theorem

I am struggling to spot how $\left(g^a\right)^\frac{p-1}{2}\equiv g^\frac{p-1}{2} (\mod{p})$ when $p$ is prime greater than $3$, $a$ is odd and $g$ is a primitive root modulo $p$. How does Fermat’s ...
1
vote
0answers
41 views

Class number of $\mathbb Q(\sqrt{10}) $

I am interested in knowing how to compute the class number of $\mathbb Q(\sqrt{10}) $. I am confused with these class number computations.
3
votes
2answers
46 views

If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$.

If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$. I have no idea to solve this question. Please help me to ...
0
votes
1answer
53 views

How to prove a cube minus a cube is never a cube (in whole numbers) [duplicate]

How to prove $x^3-y^3\neq z^3$ where $x$, $y$, and $z$ are whole numbers (integers greater than zero)?
3
votes
1answer
24 views

An identity for $J_n(x)$

It was much easier and faster to upload the image of my proof. I got it down to where the question marks are. But I can not seem to figure out how to get the anti-derivative to evaluate the integral. ...
4
votes
1answer
35 views

is there a negative integer which is a quadratic residue mod every prime $p\equiv 7\mod 8$

Is there a negative integer $n < 0$ such that the congruence $x^2 = n\mod p$ is solvable for every prime $p\equiv 7\mod 8$? If we remove the negativity condition it's well known that $n = 2$ ...
2
votes
1answer
28 views

Lagrange Multipliers for farthest distance

I am trying to find the farthest point from the origin to a point on the circle $$(x-2)^2+y^2=1$$ I am not great with the formatting on here but this is what I have so far... $$f(x,y)=x^2+y^2 $$ ...
8
votes
0answers
71 views

Proving that the number of integer solutions of $x^2-Ny^2=1$ is infinite

I am trying to prove that the number of integer solutions of $x^2-Ny^2=1$ is infinite whenever N is a squarefree integer. For this I define norm of $a+b\sqrt N=a^2-Nb^2$. Now I prove that $a+b \sqrt ...
0
votes
2answers
49 views

Proving that a summation is multiplicative

I have been give a project for number theory: For $m>0$ , let $f(m) = \sum_{r=1}^m \frac{m}{\gcd(m,r)}$ . Evaluate $f(m)$ in terms of the prime factorization of $m$. So far, I have found a formula ...
0
votes
0answers
18 views

explicitly splitting the hamilton quaternions over local fields

For simplicity, lets first consider the hamilton quaternions $$ H = \left(\frac{-1,-1}{\mathbb{Q}}\right)$$ This is the central division algebra over $\mathbb{Q}$ with $\mathbb{Q}$-basis given by ...
1
vote
0answers
13 views

$x\in\mathcal{O}_K$ can be written as product of irreducible elements

Lemma: Every element $x\neq 0$ of $\mathcal{O}_K$ with ($K$ an arbitrary number field) can be written as a product of irreducible elements. Proof: We prove this lemma by complete induction on ...
3
votes
1answer
41 views

Power to which 7 is raised to produce a number starting with 2015…

Q. Is there a power of 7 such that the number produced starts with 2015? I am completely stumped and any hints towards the solution would be great, bear in mind this is a question posed to a student ...
0
votes
2answers
19 views

Can some of the case of this congruence be solvable? And what is the general way to solve this if it is solvable?

$a^m$ congruence to 1 (mod n) where a and n is not a coprime and m is an integer. How do you prove it if it is not solvable?
0
votes
0answers
12 views

How does class field theory help us deduce the splitting of nonprincipal prime ideals?

I had a general question about the significance of global class field theory. One of the goals, as I understand, is to answer the following question: Given $L/K$ abelian, $g$ a divisor of $[L : ...
0
votes
2answers
33 views

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ and $\phi(mn)=m\phi(n)$

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ and $\phi(mn)=m\phi(n)$. My attempt. As every prime that divides $n$ also divides $m$, this implies that $(m,n)=d$ ...
2
votes
1answer
37 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
1
vote
0answers
38 views

Integers points of an elliptic curve

I am concerned by the number N of integer points in some class of elliptic curves. It is known to be finite for each elliptic curve C the corresponding bound being a function $N_C$ which gives a huge ...
2
votes
1answer
15 views

number of weak compositions modulo prime $p$

For $n\in \mathbb{N}$ and some prime $p$, consider $(\mathbb{F}_p)^n$. Is it known how many weak compositions $$x_1+x_2+\ldots +x_n\equiv 0 \pmod p$$ in $\mathbb{F}_p$ there are, where $(x_1, \ldots, ...
1
vote
0answers
35 views

Quadratic Field of $Q[√−1]$… [on hold]

Can someone show me a complex plane around the origin, with the points on the part of the complex plane which are quadratic integers in $Q[√−1]$. Another graph for $Q[√−3]$. And another for $Q[√−5]$. ...
1
vote
1answer
57 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.