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)

1
vote
0answers
55 views

$c$ primitive root, $a \in \{1,\ldots,p-1\}, w/ j \in \mathbb Z^+, a \equiv c^j \pmod p), a^{\frac{p-1}{2}} \equiv 1 \pmod p\implies j\text{ even}$.

Suppose c is a primitive root modulo $p$. Suppose you have a particular integer $a \in \{1,2,\ldots,p-1\}$ and you have found $j \in \mathbb Z^+$ such that $a \equiv c^j\pmod p$. Show that if ...
5
votes
1answer
216 views

Prime gaps with respect to the squared primes

Conjecture If we have two consecutive prime numbers $p_{a}$ and $p_{a+1}$, and two other consecutive primes $p_n$ and $p_{n+1}$, so that $p_{a} < p_{a+1} < p^2_{n+1}$, then $p_{a+1} - ...
4
votes
2answers
402 views

Fermat's 2 Square-Like Results from Minkowski Lattice Proofs

Minkowski's Convex Body Theorem for lattices in the plane: Suppose $\mathfrak{L}$ is a lattice in $\mathbf{R}^2$ defined as $\mathfrak{L}=\{m\vec{v_1}+n\vec{v_2}:m,n\in\mathbf{Z}\}$, where ...
1
vote
2answers
101 views

$a^{(p-1)/2} \equiv \pm 1 \pmod p$

Show that if $a$ is any integer not divisible by $p$, then $a^{(p-1)/2}\equiv \pm 1 \pmod p$. I know one wants to use Fermat's Little Theorem which states if $a$ is any integer not divisible by $p$, ...
1
vote
1answer
155 views

Existence of a prime between $ap$ and $(a+1)p$ - generalization of Bertrand's postulate

Conjecture: There exists at least one prime number $p_{m}$ : $ap_{n} < p_{m} < (a+1)p_{n}$, $\forall$ $a \in \mathbb{N}$ and $\forall$ $p_{n}$ $\in \mathbb{P} $ if $(a+1)p_{n} < ...
0
votes
2answers
196 views

What is the remainder when $3^{1264}$ is divided by 549?

Please explain in detail. I tried a lot by applying normal remainder theorem but I am not able to get anywhere.
5
votes
1answer
278 views

Hard floor function problem

Let $\left \lfloor{x}\right \rfloor $ denote the floor of $x$. Supose $m\in \mathbb{N}$, and that $t$ is a positive irrational number. Put $n=\left \lfloor{mt}\right \rfloor$. Prove that ...
3
votes
1answer
106 views

How can I compute the sum of the primes (with powers) that occur in the factorization of an integer?

For example, $40=2^3\cdot 5$, so the sum $S(40)=2^3+5=13$. Also, $200=2^3\cdot 5^2$, so $S(200)=2^3+5^2=8+25=33$. For a fixed $n$, I'd like to find some properties about $S(n)$. But I could find ...
1
vote
0answers
142 views

Mathematical foundation crisis and the RSA

I am currently in my last year of high school and I am writing a report on cryptography from a idea historical and mathematical perspective. I am including a few of the subjects: Cantor's diagonal ...
0
votes
1answer
294 views

Gaussian prime proof

Prove or disprove that if $a+bi$ is a Gaussian prime, where a and b are nonzero, then $N(a+bi)$ is a rational prime. I am pretty sure that there is a theorem that states this, but I'm not sure how ...
1
vote
2answers
132 views

Prove that $\sqrt{2n^2+2n+3} $ is irrational

I have proven this by cases on $n$. I would like to see a neater proof. One similar to the proof of the fact that $\sqrt{2}$ is irrational.
3
votes
2answers
204 views

Number Theory Contest Math

Find the smallest positive integer $n$ such that $n^4 + (n + 1)^4$ is composite. Find the sum of the first $5$ positive integers $n$ such that $n^2 - 1$ is the product of 3 distinct primes. Answer to ...
3
votes
1answer
561 views

What is the use of Euler Totient or Phi Function?

What is most motivating way of introducing this function? Does it in itself have any real life applications that have an impact. I can only think of a^phi(n)=1 (mod n) which is powerful result but ...
3
votes
1answer
177 views

Convergence of Rademacher's formula: Extending the partition numbers to complex index

Consider the famous formula of Rademacher (actually Hardy, Ramanujan, and Rademacher): $$p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^{\infty} \sqrt{k}\ A_k(n)\ F_k'(n)$$ $$A_k(n) = \sum_{0 \le m < k, ...
0
votes
2answers
35 views

divide 100 in to 5 spots with each spot getting twice as much as the one before

OK, so say I have $100 and I want to break it up between 5 people, but I want to make is so every person gets twice as much as that last person... What % would each person get? How would I get this? ...
1
vote
1answer
114 views

Counting Solutions of a Quadratic Diophantine Equation

How can one construct a function $f(n)$ that counts the number of solutions of the equation $$x^2+y^2-n(x+y) = 0,\quad x,y\in\mathbb{Z},$$ where $n\in\mathbb{Z}^+$? For example, we have ...
0
votes
2answers
94 views

sum over primes less than 'x

is there a function $ f(x) $ so $$ \sum_{p\le x}f(p)=S(x)$$ where $ S(x)=g(f(x), \pi(x) $ this means that the sum S(x) depends on the function $ f(x)$ but also on the prime number counting ...
2
votes
2answers
74 views

Orthogonality de Möbius

Does anyone know how prove that $$\sum_{n\leqslant x}\mu(n)\xi(n) =o(x)$$ when $\xi(n)$ is a multiplicative functions? I found one commentary that exist a connection of this problem with the Theory of ...
5
votes
1answer
141 views

Injectivity of the function n times the Euler Totient of n

Let $f: \mathbb{N} \to \mathbb{N}$ defined by $$f(n) = n \varphi(n),$$ where $\varphi(n)$ is the Euler Totient function. Prove that f is injective.
5
votes
1answer
88 views

About $S_n=\{(x,y)\mid \lfloor kx\rfloor=\lfloor ky\rfloor,k=1,2,\cdots n;~x,y\in [0,1]\}$

Let $$S_n=\{(x,y)\mid \lfloor kx\rfloor=\lfloor ky\rfloor,k=1,2,\cdots n;~x,y\in [0,1]\}$$ Here are the pictures of $S_1,S_2,\cdots S_{10}$: We can see that $S_1$ has only one blue region, $S_2$ ...
2
votes
2answers
106 views

Prove that $f(n)$ is the nearest integer to $\frac12(1+\sqrt2)^{n+1}$?

Let $f(n)$ denote the number of sequences $a_1, a_2, \ldots, a_n$ that can be constructed where each $a_i$ is $+1$, $-1$, or $0$. Note that no two consecutive terms can be $+1$, and no two ...
3
votes
4answers
421 views

Find the remainder when $2^{47}$ is divided by $47$

So I am trying to work out how to find remainders in several different way. I have a few very similar question, 1.) Find the remainder when $2^{47}$ is divided by 47 So i have a solution that says ...
1
vote
1answer
74 views

Show that if an odd perfect number exists, it must be divisible by at least 3 different primes

I would assume you'd start by showing that $\dfrac{p}{p-1}\cdot\dfrac{q}{q-1}< 2$ but I don't know how to show that nor how to continue afterwards
18
votes
1answer
441 views

Class group and factorizations

There is a common characterization of the class group ${\rm Cl}(R)$ as a kind of measure of how badly factorization fails to be unique. The most obvious justification for this sentiment is that the ...
1
vote
1answer
101 views

Prime Factors of Cyclotomic Polynomials

I'm trying to show that if $q$ is a prime and $f_{q}(x)$ is the $q$-th cyclotomic polynomial, then all prime divisors of $f_{q}(a)$ for some fixed $a \neq 1$ either satisfy $p \equiv 1\, \text{mod}\; ...
1
vote
2answers
189 views

Let p, q, r be distinct primes greater than 3, and let n = pqr.

Show that if $x \in \mathbb{Z}$ satisfies $x^{2} \equiv 9\mod{n}$ then $x \equiv ±3 \mod{p}$, $x \equiv ±3 \mod{q}$ and $x \equiv ±3 \mod {r}$. I'm not sure what to do. Any help is ...
1
vote
1answer
40 views

Good encryption exponent

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are ...
3
votes
1answer
104 views

Orbits of $\mathbb{Z}_n^{*}$ acting on a set $\mathbb{Z}_n$

Let $n\geq 2$ be an integer and consider the action $\Phi: \mathbb{Z}_n^{*}\times \mathbb{Z}_n \rightarrow \mathbb{Z}_n$ defined as $$\Phi(\alpha)(x)=(\alpha x \textrm{ mod } n),$$ i. e. simply the ...
4
votes
1answer
366 views

Finite abelian unramified $p$-extension of a number field

Let $K$ be a number field. How many finite abelian unramified $p$-extensions of $K$ are there and what are their Galois groups? My feeling is, that every group $\mathbb{Z} / p^n \mathbb{Z}$ can occur ...
2
votes
1answer
90 views

Do there exist natural number solutions such that $x^m=11\cdots11$ for $m\ge 2$?

Let us consider $R_n:=\frac{{10}^n-1}{9}=11\cdots1$. Let $m\ge 2\in\mathbb N$. Question : Do there exist natural number solutions such that $x^m=R_n$ for $m$ such that $(m,10)=1$ ? Here, ...
11
votes
2answers
507 views

How does one attack a divisibility problem like $(a+b)^2 \mid (2a^3+6a^2b+1)$?

In my current line of investigation, I am running into [many] divisibility questions like the one in the title, i.e. $$ (a+b)^2 \mid (2a^3+6a^2b+1), \qquad(\star) $$ where $a > b \ge 1$ are ...
3
votes
2answers
162 views

Pigeonhole Principle - numbers between $1$ and $100$

Of the set $A=${$1,2,...,100$}, we will choose $51$ numbers. Prove that, among the $51$ chosen numbers, there are two such that one is multiple of the other My notes: 1) There are $25$ prime numbers ...
0
votes
1answer
64 views

Suppose $gcd(a,n)=1$. If $a^x\equiv b\pmod n$ and $xy\equiv 1\pmod {\phi(n)}$, show that $a\equiv b^y\pmod n$.

My midterm exam is coming and I have some problem in dealing with this kind of question. This is an exercise on my text book and not a homework. Suppose $gcd(a,n)=1$. Question(a) If $a^x\equiv ...
5
votes
1answer
232 views

Efficient division using binary math

I'm writing code for an FPGA and I need to divide a number by $1.024$. I could use floating and/or fixed point and instantiate a multiplier but I would like to see if I could do this multiplication ...
1
vote
4answers
2k views

Simple algorithm to get the square of an integer using only addition?

This problem was mentioned in passing in a reading and it piqued my curiosity. I'm not sure where to start. Any pointers? (perhaps square root was meant?)
0
votes
1answer
65 views

Solve: $ \dfrac{x}{k_1} + \dfrac{y}{k_2}=z $ when $ x+y \neq z$

If $\gcd(x,y,z)>1$, any hint on how to find all the non-zero pairs $(k_1, k_2) \in \mathbb{Z^2} $ such that $ \dfrac{x}{k_1} + \dfrac{y}{k_2}=z $ when $ x+y \neq z$?
3
votes
1answer
197 views

What is $a^n\bmod n$ for composite $n$?

While Fermat's little theorem states that $$a^p\equiv a\pmod p$$ for any prime number $p$, which may be considered a consequence of Euler's theorem $$a^{\phi(n)}\equiv 1\pmod n\tag{e}\label{e}$$ (for ...
0
votes
1answer
163 views

How many distinct (non-isomorphic) field extensions of degree n are there?

My study group ha raised an interesting question. Up to isomorphism, how many field extensions of degree n are there? Since a field extension is by definition a vector space, they are all isomorphic ...
2
votes
1answer
107 views

Number of points on $Y^2 = X^3 + A$ over $\mathbb{F}_p$

Let $p\equiv 2\pmod{3}$ be prime and let $A\in\mathbb{F}^{∗}_p$ . Show that the number of points (including the point at infinity) on the curve $Y^2 = X^ 3 + A$ over $\mathbb{F}_ p$ is exactly $p + 1$ ...
5
votes
1answer
119 views

Are most numbers of the form $a\cdot b^n+c$ composite?

It seems evident that for $a,b,c$ with $a>0$ and $b>1$ that there are only $o(x)$ primes of the form $a\cdot b^n+c$ with $n\le x.$ Has this been proven? Hooley (Applications of Sieves to the ...
4
votes
0answers
69 views

Solve $f(x)\mid g^2(x)+1$ in $\mathbb Z[x]$

We know that if $p\in \mathbb P$ and $p\equiv 1\bmod 4$ then we can find $t\in\mathbb Z$ such that $p\mid t^2+1.$ For what polynomial $f(x)\in \mathbb Z[x]$, we can find $g(x)\in \mathbb Z[x]$ ...
0
votes
3answers
51 views

Will modulus give me $n - 1$?

Say I divide a number by 6, will a number modulus by 6 always be between 0-5? If so, will a number modulus any number (N) , the result should be between $0$ and $ N - 1$?
2
votes
1answer
191 views

Irrationality/Transcendentality of values of $e^{e^x}$

1) Is $e^{e^x}$ irrational for all rational $x$? It is known that $e^x$ is transcendental for every nonzero algebraic $x$. But this dos not help here because for transcedental $x$, $e^x$ can be ...
1
vote
1answer
62 views

Gaussian Norms problem if and only if

Problem: Suppose $p$ is a prime number. Prove that $p$ is irreducible in $\Bbb Z[\sqrt{−5}]$ if and only if there does not exist $\alpha \in \Bbb Z[\sqrt{−5}]$ such that $N(\alpha) = p$. ...
2
votes
2answers
201 views

Do Hyperreal numbers include infinitesimals?

According to definition of Hyperreal numbers The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers greater than anything of the form 1 + 1 + 1 ...
2
votes
1answer
251 views

Prove that for each $n$, there are $n$ consecutive integers, each of which is divisible by a perfect square larger than $1$ [closed]

Prove that for each $n$, there are $n$ consecutive integers, each of which is divisible by a perfect square larger than $1$.
4
votes
0answers
67 views

Can we say anything about the structure of the semigroup of non-coprime pairs after this?

Let $S = \{(a,b) : \ a, b \in \Bbb{Z} \wedge \gcd(a,b) \neq 1 \}$. Then it forms a semigroup under componentwise multiplication and if we add an exception, that even though $\gcd(1,1) = 1$, we ...
0
votes
2answers
129 views

Using induction to prove that every integer can be written in a particular form

(a) Use induction to prove that every integer $n$ can be written in the form: $$n = \beta_0 3^0 + \beta_1 3^1 + \cdots + \beta_{r-1} 3^{r-1} + \beta_r 3^r$$ where $r$ is a non-negative ...
0
votes
1answer
104 views

least residue primitive roots number theory

Let $p$ be an odd prime and let $g$ and $h$ be primitive roots of $p$. Fix $a=1,2,3\ldots p-1$. We know there exist integers $i$ and $j$ such that $g^i\equiv a\pmod{p}$ and $h^j\equiv a\pmod{p}$. ...
2
votes
3answers
66 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...