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
0answers
9 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 ...
3
votes
0answers
24 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
0answers
13 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
96 views

Fermats 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 Fermats ...
0
votes
0answers
32 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
32 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
49 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. ...
3
votes
1answer
32 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
27 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 $$ ...
7
votes
0answers
66 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
43 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
16 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
12 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
35 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
18 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
8 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
22 views

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

If every prime that divides $n$ also divides $m$, show that $\phi(mn)=n\phi(m)$ & $\phi(mn)=m\phi(n)$ My attempt. As every prime that divides $n$ also divides $m$ implies $(m,n)=d$ where ...
2
votes
1answer
35 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
33 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
14 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
33 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
49 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.
1
vote
3answers
46 views

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$ Attempt: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies ...
1
vote
1answer
10 views

What other types of distributivity are there?

When I say ‘Distributivity,’ I mean the way a number $x$ can be ‘Put in to’ some other function or the like. For example, to distribute $x$ into $\text{id}_y$, you simply have ...
-1
votes
2answers
47 views

A bizarre property [duplicate]

Studing some fact about p-adic numbers I read a bizarre property. A metric space S is called ultrametric when $d(x, y) \le\max\{d(x, z), d(z, y)\} \forall(x,y,z) \in S^3$. Prove that all ball of S ...
0
votes
1answer
21 views

Primes in Quadratic Fields with Norm less than 6

What are the primes in $\mathbb Q[\sqrt{−1}]$ which have norm less than $6$? Also what primes in $\mathbb Q[\sqrt{−3}]$ have norm less than $6$, and the primes in $\mathbb Q[\sqrt{−5}]$? Which of them ...
1
vote
0answers
45 views

Class Group of $\mathbb Q(\sqrt{-15})$

Class Group of $\mathbb Q(\sqrt{-15})$ I used this paper for my attempt. First the discriminant of $\mathbb Q(\sqrt{-15})$ is the discriminant of the monic minimal polynomial of ...
0
votes
2answers
39 views

What do you call the subset of all the Gaussian integers having the smallest magnitude given an argument?

How is called the subset of Gaussian integers such that from all Gaussian integers having the same argument only one with the smallest absolute value is included? Is there a special name for them? ...
0
votes
1answer
22 views

Show that $ζ$ is a Quadratic Integer in $Q[\sqrt{−3}]$

So in the complex plane, there are three cube roots of one. Suppose we let $ζ$ be the cube root of one which has positive imaginary part. How can we show that $ζ$ is a quadratic integer in ...
1
vote
1answer
52 views

How Deficient a Number is? (Finding numbers having a certain deficiency)

This question was edited, in particular equations were corrected: A number N is said to be deficient by an integer $d$ if: $\sigma(N)=2N-d$ Note that powers of 2 are deficient by 1. While a prime ...
0
votes
2answers
31 views

Purely number theory problems

Suppose the numbers $1,2,3,\dots,1986$ in any order are concatenated then prove that the number is not a perfect cube. This problem gives me a feeling that here cubic residues can only help no other ...
2
votes
1answer
31 views

Average difference between two odd numbers of equal length

If I select two different odd numbers of binary length $l$, what is the formula that will tell me the average difference between those two numbers? Note that the high order digit must always be $1$, ...
11
votes
1answer
159 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
0
votes
1answer
37 views

What is the number of complex integers inside a circle of radius r? [on hold]

What is the number of such complex integers, $z$, that $|z|\le r$? I am interested in a closed-form formula for integer $r$.
-1
votes
2answers
53 views

Solving $a^2$ $+$ $ b^2$ $=$ $2c^2$ [on hold]

I was working through some number theory problems , when I came across the following question : Find all solutions of $a^2$ $+$ $b^2$ $=$ $2c^2$ Can someone help me out ? Maybe a hint ...
9
votes
4answers
347 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
7
votes
3answers
101 views

Irrational Numbers : Show that $0.1248163264…$ is irrational

I was working through some basic Number Theory Problems in Rosen and came across the following problem : Show that the real number $0.1248163264...$ represented in ...
4
votes
3answers
34 views

Largest subset with no arithmetic progression

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original ...
5
votes
3answers
56 views

For any 7 different real numbers, there are among them two numbers x and y such that $0<\frac{x-y}{1+xy} < √3$

For any 7 different real numbers, there are among them two numbers x and y such that $\frac{x-y}{1+xy}$ is greater than zeron and less than the square root of 3. I find this fact quite amazing for ...
4
votes
4answers
119 views

How to solve $x^3\equiv 10 \pmod{990}$? [on hold]

How to solve $x^3\equiv 10\pmod{990}$? It has 3 solutions: 10, 340, 670. Here is the link: https://www.wolframalpha.com/input/?i=x%5E3+%3D+10+%28mod+990%29
0
votes
1answer
68 views

Prove that there are infinitely many primes in $\mathbf Q[\sqrt{d}]$.

Prove that there are infinitely many primes in $\mathbb Z[\sqrt{d}]$. I don't know how to prove this, but I think that the proof will be similar to proving that there are infinitely many primes in ...
-2
votes
1answer
64 views

Is there an arbitray large prime equal to 3k+2? [duplicate]

How could I find an arbitray large prime number equal to 3k+2?
-4
votes
1answer
36 views

If two integers are associates then their norms are equal in absolute value [on hold]

In $Q[\sqrt{d}]$ prove that if two integers are associates then their norms are equal in absolute value when $d>0$ and $d<0$
2
votes
1answer
19 views

Infiniteness of set of primes such $f$ have root $\mod p$ [duplicate]

Let $f \in \mathbb{Z}[x]$ be non constant. How to prove that exists infinitely many primes such $f$ have root in $\mathbb{Z/_{(p)}}$. I spent much time, but with no benefits.
-3
votes
0answers
22 views

define a notion of congruence [on hold]

So I am learning congruences and ring theory etc, and I have a question. If $α$ is a quadratic integer in $Q[√−d]$, then what would define a notion of congruence (meaning mod $α$). Also, how would ...
0
votes
2answers
42 views

Sum of odd Fibonacci Numbers

Trying to prove that the sum of odd-index consecutive Fibonacci numbers is the next even-index Fibonacci number. I have a gap in my proof that I cannot figure out. I know that induction would be ...
-1
votes
0answers
56 views

Choosing M cards from N decks

Alice and Bob are playing cards. They have N decks of cards. Each deck of cards contain 52 cards: ...
2
votes
0answers
14 views

norm map and local class field theory

Let $K$ be a local field, say a finite extension of $\mathbb{Q}_p$ (which is the purpose of my interest). Let $L$ be an unramified extension of $K$. Local class field theory asserts that there ...
-1
votes
2answers
25 views

Congruence Classes $(\text{mod} (3 + \sqrt{−3})/2)$ in $Q[\sqrt{−3}]$ [on hold]

What would be the congruence classes $(\text{mod} (3 + \sqrt{−3})/2)$ in $Q[\sqrt{−3}]$?