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)

2
votes
0answers
89 views

A function that generates 'alternating' non-trivial zeros of $\zeta(s)$

I am trying to find a function, that assuming RH, generates subsequent non-trivial zeros $\rho_n$ in an alternating way i.e.: $$\frac12+14.134...i,\frac12-21.022...i,\frac12+25.010...i, \dots$$ or ...
0
votes
1answer
58 views

Finite field integers

can some one explain the following terms $Z_n^N$, $F_q^N$ and $F_q^*$ and why the bi-linear pairing is used in cryptography.
2
votes
2answers
50 views

theorem dealing with order of numbers

I'm having trouble understanding part of the proof to a theorem. The theorem states that Let $ord_ma = e$ and k any positive integer. Then $ord_m(a^k)$ = $e/(e,k)$. The part I don't understand is ...
0
votes
1answer
40 views

Show that $(p^{n+1} - 1)/(p -1)$ is even if and only if $n+1$ is even

Show that if $p \in \mathbb{Z}_+$ is odd and $\geq 3$, and $n \in \mathbb{Z}_+$, then $(p^{n+1} - 1)/(p -1)$ is even if and only if $n+1$ is even, and $(p^{n+1} - 1)/(p-1) \equiv 0 \mod 4$ if and ...
1
vote
4answers
83 views

I cannot find the last factor of this expression?

I'm supposed to factor $x^8-y^8$ (the exponents are 8 for both if it is too difficult to see) as completely as possible. It is easy to factor this to $(x+y)(x-y)(x^2+y^2)(x^4+y^4)$. However, the book ...
9
votes
3answers
703 views

Size of largest prime factor

It is well known and easy to prove that the smallest prime factor of an integer $n$ is at most equal to $\sqrt n$. What can be said about the largest prime factor of $n$, denoted by $P_1(n)$? In ...
0
votes
1answer
198 views

Proving that a number with digits 1…9 in some order, ending in 5, is not a perfect square.

If "x" is a 9 digit number , which contains digits from 1 to 9 which ends in 5 . Prove that it can't be a perfect square ( digits are not to be repeated). Please suggest the solution of this ...
3
votes
1answer
77 views

Easy way to calculate $614^7 \pmod{2609}$?

We are starting to go over Cryptography in our Number Theory class and we are doing an example of encrypting a message using something similar to RSA method. I have I need to find what $$614^7 ...
2
votes
1answer
861 views

number of terms of a sum required to get a given accuracy

How do I find the number of terms of a sum required to get a given accuracy. For example a text says that to get the sum $\zeta(2)=\sum_{n=1}^{\infty}{\frac{1}{n^2}}$ to 6 d.p. of accuracy, I need to ...
2
votes
1answer
139 views

Interesting question about irrational numbers

Find all solutions in un-ordered integers $(a,b)$ to $7-a-b=2\sqrt{10}-2\sqrt{ab}$. It would appear that the only solution to this is $a=2, b=5$. But how to prove this rigorously? Do irrational ...
4
votes
3answers
144 views

Let $f(n)$ be the number of prime factors of the positive integer $n$. Find $\lim_{n\to \infty}\frac{f(n)} n$

Let $f(n)$ be the number of prime factors of the positive integer $n$. Find $\displaystyle \lim_{n\to \infty}\frac{f(n)} n$. I suspect it's equal to $0$, but how can I show this? Thank you.
1
vote
1answer
115 views

Finding quadratic residues in a finite field by using a primitive element

Let $1+2x$ be a primitive element of the field $\mathbb F_9$ obtained via the irreducible polynomial $$x^2 + 1$$ over the base field $\mathbb F_3$. i) Make a list of the elements of $\mathbb F_9$ ...
-1
votes
3answers
79 views

Cryptology number theory

By using Chinese Remainder Theorem, how many solutions are there to $b^{1104} = 1 \pmod{5*13*17}$ with $gcd(b, 1105) = 1$?
1
vote
1answer
116 views

Reformulation of riemann zeta

Does this extend to $\mathbb{C}$? $\displaystyle ζ(x) = \int_0^{\infty} \frac{ 1}{\lfloor t\rfloor ^x} dt$, where for $0 \leq t < 1$ we say that $\lfloor t \rfloor = 1$.
1
vote
2answers
412 views

Mapping from 1D line to 2D plane: an infinite piece of rope covering 2D plane without self-intersection

I believe I'm looking for a function: $f(x) : \mathbb N \mapsto \mathbb N^2$ and it's inverse $f^{-1}(x) : \mathbb N^2 \mapsto \mathbb N$, a known mapping that can take any positive integer and map ...
2
votes
3answers
46 views

Prove that $\forall$ n $\in$ $\mathbb{N}$ $7^n\equiv 1 \bmod{20}$ iff $n=4k$ [closed]

Prove that $\forall$ n $\in$ $\mathbb{N}$ $7^n\equiv 1 \bmod{20}$ iff $n=4k$
40
votes
6answers
2k views

Is $\sqrt[3]{p+q\sqrt{3}}+\sqrt[3]{p-q\sqrt{3}}=n$, $(p,q,n)\in\mathbb{N} ^3$ solvable?

In this recent answer to this question by Eesu, Vladimir Reshetnikov proved that $$ \begin{equation} \left( 26+15\sqrt{3}\right) ^{1/3}+\left( 26-15\sqrt{3}\right) ^{1/3}=4.\tag{1} \end{equation} $$ ...
1
vote
0answers
97 views

Representing a fraction as a $p$-adic number

If we have the following $p$-adic number: $$2+3p+5p^2+2p^3+3p^4+5p^5+2p^6+3p^7+5p^8+.....$$ and I am trying to find what rational number this p-adic number represents. I have no idea as to how to go ...
3
votes
2answers
73 views

Is $\sum\limits^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}$?

Let $n$ be a positive integer such that $n+1$ is a prime power. That is, to illustrate $n+1$ is $9$ or $25$. Prove that $$\sum^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}.$$ Hint: I ...
0
votes
1answer
148 views

Sum of the Hyperharmonic\Over-harmonic Series under $\mathbb{Z}_n$ for $p=2$

For $n \geq 5$ prime number, calculate the sum of: $$1 + \frac{1}{2^2} + \frac{1}{3^2} + \cdots + \frac{1}{(n-1)^2}$$ under $\mathbb{Z}_n$. I figured it's the hyperharmonic\over-harmonic series, $$ ...
3
votes
2answers
197 views

Approximation to any real number by rationals

Given a real number $x$, one can show that there exists infinitely many $p,q$, such that $\gcd(p,q)=1$, and $|x-\frac{p}{q}|\leq \frac{1}{q^2}$. (There is a hint saying that I should use the pigeon ...
6
votes
1answer
154 views

Analytically continue a function with Euler product

I would like to estimate the main term of the integral $$\frac{1}{2\pi i} \int_{(c)} L(s) \frac{x^s}{s} ds$$ where $c > 0$, $\displaystyle L(s) = \prod_p \left(1 + \frac{2}{p(p^s-1)}\right)$. ...
1
vote
2answers
160 views

Show that there are infinitely many primes which are $\pm 1 \mod 5$

Show that there are infinitely many primes which are $\pm 1 \mod 5$. HINT: Suppose that there are finitely many such primes, and let these primes be $q_i$ for $1 \leq i \leq n$. Let $$N = ...
8
votes
2answers
1k views

When is the group of units in $\mathbb{Z}_n$ cyclic?

Let $U_n$ denote the group of units in $\mathbb{Z}_n$ with multiplication modulo $n$. It is easy to show that this is a group. My question is how to characterize the $n$ for which it is cyclic. Since ...
1
vote
2answers
57 views

Integer proof equivalence class

I've been searching online but I couldn't find help on this matter. How can I prove that $[(a,b)]+[(c,d)]=[(a+c,b+d)]$ is independent of the choice I make of representatives of the equivalence ...
2
votes
3answers
85 views

How to find $\gcd(a^{2^m}+1,a^{2^n}+1)$ when $m \neq n$?

How to prove the following equality? For $m\neq n$, $\gcd(a^{2^m}+1,a^{2^n}+1) = 1 $ if $a$ is an even number $\gcd(a^{2^m}+1,a^{2^n}+1) = 2 $ if $a$ is an odd number Thanks in advance.
6
votes
2answers
70 views

Need to state “$p$ not equal to $61$” when solving $61p + 1 = n^2$?

In the pictures below, am I wrong to say that the 3 lines in the red box are not needed in the solutions? Regardless of whether 61 and p are distinct, it's still true that we have only the 2 possible ...
0
votes
2answers
78 views

If $x = a + b$, and only $x$ is known, how to solve what is $a-b$?

If $x$ equals to $a+b$, how can I solve what is $a-b$, knowing only $x$? (approximation will do as well, if it cannot be solved exactly)
1
vote
2answers
73 views

Some basic properties of Pisot number

A Pisot number is an algebraic integer $>1 $ and all of whose conjugates have modulus $<1$. First assume that $q$ is a Pisot number. Denote by $q_1,\ldots, q_d$ the algebraic conjugates of ...
0
votes
1answer
109 views

Find if a number $n$ is a primitive root of $p$

Let $n = p_1\cdot p_2\cdot\ldots\cdot p_k$ where the $p_i$ are primes. Let $s = \varphi(n)$ where $\varphi$ denotes the Euler Totient Function. If none of $p_1,p_2,\ldots,p_k$ makes $a^{(s/p_i)} = 1$ ...
7
votes
1answer
314 views

Dirichlet's theorem on arithmetic progressions

The theorem can be found on Wikipedia. In the subsection "Proof" Wikipedia says that there is a proof for the case $a=1$ which uses no calculus, instead splitting behavior of primes in cyclotomic ...
1
vote
1answer
91 views

Prove that $\frac{m+n+2}{2(m+1)}{n\choose m}2^{(n-m)/2}$ is an integer

Let $m,n$ be positive integers, both odd or both even, with $n\ge m$. I think the following number $$\frac{m+n+2}{2(m+1)}{n\choose m}2^{(n-m)/2}$$ is always an integer, but I have trouble proving it.
3
votes
3answers
96 views

The number $ \frac{(m)^{(k)}(m)_k}{(1/2)^{(k)} k!}$

For a real number $a$ and a positive integer $k$, denote by $(a)^{(k)}$ the number $a(a+1)\cdots (a+k-1)$ and $(a)_k$ the number $a(a-1)\cdots (a-k+1)$. Let $m$ be a positive integer $\ge k$. Can ...
3
votes
2answers
75 views

Is it true that $\mathbb{Z}_{(p)}=\mathbb{Z}_{p}\cap \mathbb{Q}$?

I know $\mathbb{Z}_{(p)}\subset \mathbb{Z}_{p}\cap \mathbb{Q}$, where $\mathbb{Z}_{(p)}$ is the localization of $\mathbb{Z}$ at prime ideal $(p)$ and $\mathbb{Z}_p$ is the set of p-adic integers. I ...
2
votes
0answers
60 views

An identity related to Chebyshev polynomial

Let $n=2m$ be a positive even integer. I can prove that $$1+\sum_{k=1}^m (-1)^k \frac{n^2(n^2-2^2)\cdots(n^2-(2k-2)^2)}{(2k)!}=(-1)^m$$ using hypergeometric identity ...
1
vote
3answers
303 views

Computing large modular numbers

How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, ...
3
votes
2answers
71 views

Modular Exponentiation

Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$ I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
2
votes
3answers
631 views

All group homomorphism from $ \mathbb{Z} _m $ to $\mathbb{Z}_n $ [duplicate]

All group homomorphism from $ \mathbb{Z} _m $ to $ \mathbb{Z}_n $ How could I find every group homomorphism?
8
votes
3answers
482 views

$1+x+\ldots+x^n$ perfect square

Let $p$ be the polynomial $p(x)=1+x+\ldots+x^n$. For which couples $(a, n)\in\mathbb{N}^2$, $p(a)$ is a perfect square? I'm particularly interested in $p(3)$.
1
vote
0answers
86 views

To prove $\frac {a^2+b^2}{ab+1}$ is a perfect square , without geometry or induction. [duplicate]

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$ ; then prove that $\frac {a^2+b^2}{ab+1}$ is a perfect square (this problem came in $\Bbb {IMO}$ $1988$). How to prove it ...
4
votes
1answer
87 views

$\sum_{m=1}^\infty \frac {2^{\widehat m}+2^{-\widehat m}}{2^{m}} =3$

For any positive integer $n$ , let $\widehat n$ denote the integer nearest to $\sqrt n$. Then how to prove that $$\sum_{m=1}^\infty \frac {2^{\widehat m}+2^{-\widehat m}}{2^{m}} =3$$?
3
votes
3answers
366 views

Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)

Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which ...
2
votes
3answers
159 views

Root of multiplicity?

Show if a is a root of multiplicity $n\geq 2\ $, then $f(a) = 0$ and $f'(a)=0.$ I was trying to learn root of multiplicity and saw this question. My TA did not go over it yet but I was wondering how ...
19
votes
2answers
12k views

Has anyone found a “pattern” in prime numbers?

Yesterday I was having some fun trying to look for some patterns in primes; and I think I found something interesting (to me at least). I still have not found any lists of patterns already found, ...
3
votes
2answers
60 views

Subgroups that can be proven?

How do you show all subgroups of $A_5$ have order less or equal than 12? I know you can use this lemma: If G is a finite group, and H does not equal G is a subgroup of G such that oG $/|/$ i(H)! ...
1
vote
2answers
92 views

Pigeon hole principle question

Their are a group of finite aliens on a spaceship. Show that their are at least two aliens who know the same number of aliens on the spaceship. I was given a hint, and that was to use the pigeon ...
5
votes
2answers
154 views

To estimate $\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$

How may we estimate $$\sum_{m=1}^n \Big(d\big(m^2\big)\Big)^2$$ where for every positive integer $m$ , $d(m)$ denotes the number of positive divisors of $m$ ?
2
votes
1answer
114 views

Ordinary generating function for Bernoulli polynomial

I know the exponential generating function for the Bernoulli polynomial $B_n(x)$:$$\frac{te^{tx}}{e^t-1}=\sum_{n=0}^\infty B_n(x)\frac{t^n}{n!}.$$ But is there an ordinary generating function? i.e a ...
3
votes
1answer
121 views

How can 0.149162536… be normal?

I was reading about normal numbers on WikiPedia, and I ran across this statement: Besicovitch (1935) proved that the number represented by the same expression, with f(n) = n^2, ...
2
votes
2answers
47 views

Diophantine equation $(E): 49x-6y=1$

We suppose the Diophantine equation on $\mathbb{Z}*\mathbb{Z} \quad$ $(E): 49x-6y=1$ and it's general solution is: $\{(6k+1),(49k+8): k\in \mathbb{Z} \}$. We set $N = 1+7+7^2+...+7^{2007}$. How can ...