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

This expression is always a perfect square

How to show that for $x,y\in \Bbb R$, the expression $xy+\left(\frac{x-y}{2} \right)^2$ is always a perfect square? For example $x=7, y=3$, $7\times 3+\left(\frac{7-3}{2} \right)^2=25=5^2$
-1
votes
2answers
32 views

How to find $x$ value using congruences

I know congruences somewhat, however this problem is troubling me a lot. Please help me. If $17^5\equiv 5 \pmod {21}$, then at what value of x, $x^5\equiv 99 \pmod{21}$? High regards, ZION
0
votes
4answers
84 views

How many $0$s does the number $30!$ have? [duplicate]

I want to find out the number of $0$s in the number $30!$, what should I do? Is there any trick that would work for a general question of this type, like number of $0$s in $50!$ ?
1
vote
1answer
24 views

Fibonacci Cyclic Pattern

I want to show the Fibonacci numbers are cyclic in mod n. I have tried some small values for n and I can see this is the same. In terms of a proof, I'm thinking of using the pigeonhole principle of ...
1
vote
1answer
28 views

Quadratic reciprocity in the case $a=-1$

I am reading the proof the for odd prime $p$, $$ \left ( \frac{-1}{p} \right)_2 = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 \hspace{2mm} \text{for} \hspace{2mm} p \equiv 1 \operatorname{mod} 4 \\ -1 ...
0
votes
0answers
21 views

Can I do Gaussian Elimination on this? (mod 2)

I have this matrix in GF(2): [0, 0, 1, 0] [1, 1, 0, 0] [0, 0, 0, 1] It's not a square matrix but I tried to do Gaussian elimination on it anyway after adding a ...
3
votes
2answers
58 views

Simple Number Theory question! What is the remainder when 4^999 is divided by 100?

I know I'm supposed to use modular arithmetic, but I must be messing up my process somehow. Can someone explain how to do this? $4^{999}$'s last two digits in other words (What is $4^{999}$'s ...
2
votes
0answers
28 views

Let $f(x)$ be defined over all rationals $x$ in $[0,1]$ and let $F(n) = \sum_{i=1}^n f(\frac in)$

also define $$F^*(n) = \sum_{i=1\,\,(i,n)=1}^n f(\frac in)$$ then prove that $$F^* = \mu * F$$ where $\mu$ is the Möebius function and the $*$ means the Dirichlet convolution. I tried the Bell series ...
1
vote
1answer
34 views

Block of integers: Divisibility

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. (I've proved this) Suppose now a < b < ...
2
votes
1answer
42 views

Find the sum of all primes smaller than a big number

I need to write a program that calculates the sum of all primes smaller than a given number $N$ ($10^{10} \leq N \leq 10^{14} $). Obviously, the program should run in a reasonable time, so $O(N)$ is ...
1
vote
0answers
26 views

If $p\mid 2^n\pm1$ with $p$ and $n$ relatively prime, then $p$ is a Wieferich prime iff $p^2$ also divides $2^n\pm 1$

The Wolfram Mathworld article on Wieferich primes states: $2^{p-1}-1\equiv 0 \mod p.$ If the first case of Fermat's last theorem is false for exponent $p$, then $p$ must be a Wieferich prime ...
0
votes
1answer
37 views

Chinese Remainder Theorem example

$$x = 4 \bmod 18$$ $$x = 52 \bmod 96$$ $$x = 6 \bmod 20$$ My current algorithm thinks the answer is $x \equiv 1066 \bmod 1440$ but I don't think there should be a solution to this. The algorithm: ...
0
votes
0answers
19 views

Proofs needed for observations regarding prime-partitionable numbers.

Definition of a prime-partitionable integer taken from W. Holsztynski, R. F. E. Strube, Paths and circuits in finite groups, Discr. Math. 22 (1987) 263-272, doi and apparently the same as in W. T. ...
2
votes
1answer
35 views

solutions for Diophantine equation for ${k_1} + 2{k_2} + 3{k_3} + … + n{k_n} = n$

Consider the Diophantine equation of the form ${k_1} + 2{k_2} + 3{k_3} + .... + n{k_n} = n$, where ${k_1},{k_2},...{k_n} \in Z^+$ . For a given $n$, how can I obtain the solutions of a given equation ...
9
votes
2answers
399 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
1
vote
0answers
22 views

Properties of a Semi-modulo! operation

Let $A$ be an integer with its representation in base $p$ ($p$ may be prime number but not necessarily) described as: $$A=(a_ma_{m-1}\ldots a_1a_0)_{p}$$ We know $A\equiv (a_n\ldots a_1a_0)_{p^n}\pmod ...
-4
votes
0answers
37 views

How is named this property of zero parity? [on hold]

How is named then this property of zero parity? Numbers parity Any number, except zero, multiplied twice, is an even number. A pair has two elements. Demonstration: One multiplied ...
5
votes
2answers
235 views

Inequality involving a product over the primes

Is there someone who is able to prove the following statement? $$\prod_{m=1}^n \dfrac{p_m-1}{p_m} \leq \dfrac{1}{\ln(n)}$$ for all integers $n >1$ where $p_m$ is the $m$-th prime number.
5
votes
2answers
124 views

Is $a=\frac{1992!-1}{3449\times 8627}$ a prime number?

Is $a=\dfrac{1992!-1}{3449\times 8627}$ a prime number ? This is a natural follow-up to that recent MSE question We know that $a$ has $5702$ digits and no prime divisor $<10^6$.
0
votes
0answers
43 views

What is the inverse function of gcd?

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
1
vote
1answer
31 views

Is there an isomorphism $\mathbb{C}_p \cong \mathbb{C}_q$ for primes $p \neq q$?

Let $p \neq q$ be distinct primes. Is there a field isomorphism $\mathbb{C}_p \cong \mathbb{C}_q$? Is there a field isomorphism $\mathbb{C}_p \cong \mathbb{C}$? If such an isomorphism exists, given ...
1
vote
0answers
40 views

A question on the inequality $\bigl(\pi(x+y)\bigr)^2<4\pi(x)\pi(y)$

From the answer of this post it seems highly probable that the following problem can be proved, Show that for all sufficiently large $\min(x,y)$ we will have, ...
4
votes
0answers
22 views

Maximal $n$ such the the additive partition with a given product is unique.

Given $n$, there are many tuples with $a + b + c = n,0 < a < b < c$. For large $n$, different tuples may give the same products. E.g. $2+8+9=19=3+4+12,2\times8\times9=144=3\times4\times12$. ...
1
vote
1answer
41 views

Congruence using extended GCD

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. I understand now that if we combine the two it implies ...
1
vote
2answers
47 views

Why is this congruence true?

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. How/why? I am trying to understand how this is true when ...
6
votes
2answers
44 views

$2$-adic sequence converging to $\sqrt{-7}$.

I am trying to construct a sequence in $\mathbb Q_2$ that is formed of rational numbers and converges to $\sqrt{-7}$, to prove that $(\mathbb Q, |\cdot|_2)$ is not complete. My lecturer stated that ...
0
votes
0answers
30 views

A residue question in integers

Given $N\in\Bbb N$, is it possible to find $9$ positive integers $A_j,N_i$ with $j\in\{1,2,3\}$, $i\in\{1,2,3,4,5,6\}$ such that following holds? $(1)$ $N\log N < A_j < cN\log N$ at every $j$ ...
0
votes
1answer
31 views

Prove that $\sum_{t \vert n} d^3(t) = (\sum_{t \vert n}d(t))^2$ for all $n \in \mathbb{N}$ [duplicate]

here $d(n)$ counts the number of positive divisors of $n$. I've tried 2 things: Using Bell series. But then again it just showed me that the bell series of the square of a function is not the ...
0
votes
0answers
22 views

Is there a solution to this problem on Fermat's Quotient?

We define Fermat's Quotient as $q_a = (a^p-1)/p \pmod p $ where $p$ is a prime greater than $2$. How will you prove that the only solutions of the equation $q_a=0$, $q_b=0$ and $q_{a+b}=0$ where ...
1
vote
0answers
18 views

Need my CRT work spot-checked

So I have a bunch of equations that look like this: $$k + tx \equiv a \bmod m$$ Where $t$ is the common variable I am solving for among the equations (each equation may have different values for ...
0
votes
1answer
28 views

Why does this imply a congruence does not exist?

Consider $$kx \equiv a \bmod M$$ Where $x,a,M$ are known, solving for $k$. Let $g = \gcd(M,x)$. Why is it the case that if $g$ does not divide $a$, there is no solution?
4
votes
1answer
94 views

Possible proof of Fermat's Last Theorem for prime exponents greater than 2

I would appreciate if someone could check my attempt in proving the Fermat's Last Theorem for prime exponents greater than $2$. Firstly, let's prove a couple of lemmas which state that sum or ...
2
votes
0answers
36 views

Why is it so hard to find a generating function for Somos' sequence?

The sequence is $\{1,2,12,576,1658880,\dots\}$. The $n$th number is obtained by squaring the $(n-1)$-th number and multiplying by $n$. So we start with $a_1=1$, $a_2=1^22=2$, $a_3=(1^22)^23=12$. In ...
4
votes
0answers
64 views

rationality of $\ell$-adic representation attached to an elliptic curves

Let $E$ be an elliptic curves defined over a number field $K$. Consider the $\ell$-adic representation attached to $E$ $$ \rho_{\ell}:\mathrm{Gal}(\overline{K}/K) \longrightarrow ...
4
votes
1answer
61 views

Question about Mersenne numbers

We don't have any proof for Mersenne conjectures, but is it true that there exist infinitely many primes $p$ such that $2^p-1$ is not prime?
0
votes
0answers
14 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
3
votes
1answer
87 views

The existential theory is undecidable

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
0answers
47 views

Are logarithms of prime numbers algebraically independent?

From Baker's theorem it follows that a linear combination of natural logarithms of prime numbers with non-zero algebraic coefficients can never be zero. Has it been proved that the set of all natural ...
-3
votes
2answers
51 views

All natural numbers $m, n$ such that $m = \sqrt{\frac{1}3A^2 - 3n^2}$ [on hold]

I have $m = \sqrt{\frac{1}3A^2 - 3n^2}$. A is a known integer. How do I find all solutions for what m and n are if both m and n are naturals (round positive numbers)
21
votes
1answer
444 views

Is $1992! - 1$ prime?

Consider the factorials, defined inductively by $1! = 0! = 1$ and $n! = n\cdot(n-1)!$ for $n \geq 2$. Question: Is $1992!-1$ a prime number? The question is from a book, maybe is contest math ...
3
votes
1answer
43 views

Proof of Cohn's Irreducibility Criterion

I was looking for an elementary (or involving introductory level abstract algebra/analysis) proof of Cohn's Irreduciblity Criterion: If $$ a_0, a_1, \dots, a_n \in \Bbb{Z} $$ and $$ 0 \le ...
0
votes
3answers
34 views

Finding the largest square divisor of a number

My calculator has the option of representing square roots in the form of $a\sqrt b$, when $a$ is maximal. It works for very large inputs within seconds, and I wonder how it's being done.
1
vote
1answer
37 views

NumberTheory: Proof or disproof the following. Dividing and adding

Proof or disproof the following. Let $N \in \mathbb{N}$ be a natural number. If we divide the digits of $N$ with preserving the order and adding them together we will get a digit ( a number less ...
3
votes
1answer
107 views

Is the real number $\sqrt{6}$ in $\mathbb{R}$ equal to the 5-adic number $\sqrt{6}$ in $\mathbb{Q}_5$?

My question is as in the title. That is, consider solving the equation $x^2-6=0$ in $\mathbb{R}$ and in the 5-adic field $\mathbb{Q}_5$ respectively. We obtain one $\sqrt{6}\in\mathbb{R}$ and one ...
1
vote
1answer
26 views

Asymptotic probability that two integers are coprime

I'm having difficulty with a number-theory-type exercise. Could you provide assistance with computing the asymptotic probabilities that two integers are coprime (both integers tending to $\infty$), ...
1
vote
0answers
45 views

Is the Green-Tao theorem valid for arithmetic progressions of numbers whose Möbius value $\mu(n)=-1$?

I am reading the basic concepts of the Green-Tao theorem (and also reading the previous questions at MSE about the corollaries of the theorem). According to the Wikipedia, the theorem can be stated ...
3
votes
2answers
37 views

Congruence rules when solving equation

I am trying to solve the following congruence problem. 980x ≡ 1500 mod 1600 The steps I came up with were as follows: 980x ≡ 1500 mod 1600 49x ≡ 75 mod 80 (Divide by 20, gcd(20, 1600) = 20 so 80 = ...
1
vote
0answers
46 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
0
votes
0answers
24 views

On Period of Linear Recurring Sequences modulo $P^e$

If a sequence $ X_0,X_1,X_2,\ldots$ is defined in terms of an initial set $ X_0,X_1,X_2,\ldots ,X_{k-1} $ by the recurrence relation $$ X_{n+k}= ...
1
vote
1answer
14 views

Comparison of arbitary conway chains (in particular a chain with $m$ $m's$) to $f_{\omega^2}(n)$

Wikipedia describes the Conway chained arrow notation and the fast growing hierarchy. I learnt that the function $f(n):=\large f_{\omega^2}(n)$ has the same growth rate as the function ...