Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

1
vote
0answers
96 views

Trying to prove that a triangular number equation has no solutions.

I want to prove -- using elementary math only -- that the following equation has no integer solutions for $t \ge 1$: $$ 6a^2(16a^2+1) = \frac{t(t+1)}{2}. \qquad(1)$$ I know it doesn't (or at least ...
1
vote
0answers
120 views

Variation of the Principle of Mathematical Induction

Every version of weak mathematical induction I have seen is equivalent to the following statement. Let ${n_0}$ be some integer such that P(n) is some predicate defined for all integers greater than ...
1
vote
0answers
20 views

Reference for oscillation of θ(x)−x

To a question asked (in July this year) about the oscillation of θ(x)−x, Greg Martin provided the following useful response: "It is known that θ(x)−x does change sign infinitely often. I agree that ...
1
vote
2answers
82 views

'Coprime' problem related to integer rings

I am handling a problem involving the proof of whether two integers are coprime or not. Think of a positive integer $N$ and two integers $r$ and $s$ in $\mathbb{Z}_N$ such that $\gcd{(N, r)}=1$ and ...
1
vote
0answers
78 views

A Gauss sum over a field.

Let $K$ be a field (not necessarily $\mathbb C$) and let $\zeta=\zeta_n$ be a primitive $n$th root of unity in $\bar K$. I would like to know if there is a formula calculating $$ \sum_{k=1}^n ...
1
vote
1answer
260 views

Hausdorff dimension of the set of rational numbers within a certain interval?

Intro: The Hausdorff dimension (also known as the Hausdorff–Besicovitch dimension) is an extended non-negative real number associated with any metric space. In general the Hausdorff dimension ...
1
vote
0answers
48 views

Question about partitions and primes.

Let $A_1\cup A_2\cup\cdots\cup A_n = P$ , where $P$ stands for the set of odd primes $<\sqrt{x}$ and $A_i$ is nonempty. Also $\#A_k\gg \# A_l$ iff $k>l$ ($\#$ is cardinality ). In fact we ...
1
vote
1answer
58 views

Property of congruence given a square-free modulus

Problem Suppose $n$ is square-free and $\alpha,\beta,\gamma \in \mathbb{Z}_n$. I want to show that $\alpha^2 \beta = \alpha^2 \gamma \implies \alpha \beta = \alpha \gamma$. Current Work If $n$ is ...
1
vote
0answers
82 views

Prime Numbers and Primitive Roots

Let $p_1$, $ p_2$, $p_3$ different prime numbers. Let $N = p_1p_2p_3$. Given $(p_1-1)|(N-1), (p_2-1)|(N-1)$ and $(p_3-1)|(N-1)$, prove that for every number $a \in \Bbb N$ such that $\gcd(a,N) = 1$ ...
1
vote
0answers
28 views

Reasoning about $\left\lfloor\frac{p_k\#}{p_{k+1}}\right\rfloor$

This is a follow up question to my previous question. Let $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} ...
1
vote
0answers
37 views

Gap:$\;\;L(90,28) := {\{n90 - m28 ∈ N, n, m ∈ N, n < 28\}}$

Which elements of the sets Gap:$$L(90,28) := {\{n90 - m28 ∈ N, n, m ∈ N, n < 28\}}$$ $$$$What would be a quick way to resolve?
1
vote
2answers
163 views

what is the remainder when $(17^{3}+19^{3} + 21^{3}+23^{3})$ is divided by 83?

what is the remainder when $(17^{3}+19^{3} + 21^{3}+23^{3})$ is divided by 83? NOTE:$a^{3}+b^{3}=(a+b)(a^2-ab+b^2)$
1
vote
0answers
42 views

The cosets of $\mathbb{nZ}$

I'd like to show that the only cosets of $\mathbb{nZ}$ are $\bar a$ for $a=0,1,\dots,n-1$ where $\bar a$ denotes the equivalence class containing $a$. Proof. Any integer $x$ can be written as ...
1
vote
0answers
132 views

Existence of prime pairs

Will there always exist a prime pair of the form (p, p+l) for any l where gcd(p,l) = 1 and l is even? Can we always conjecture that there exist infinitely many prime pairs of the form(p, p+l) when ...
1
vote
1answer
64 views

Quadratic Diophantine Equation in Four Variables

Consider the equation: $$d^2 = 6 + a^2 - 3b^2 + 3c^2$$ where $a, b, c, d$ are integers. Is it necessarily the case that $a$ and $b$ have the same parity and that $c$ and $d$ have the opposite parity ...
1
vote
1answer
109 views

Is $\tan (\pi x)$ never rational for all rational $x$ in the interval $(-0.5,0.5)$, with the exceptions occuring at $x=0, -0.25, 0.25$?

What I'm claiming is that I have devised a proof of this statement which says that it is true. The proof is a little long and involves trigonometry and basics of number theory, so I feel lazy to ...
1
vote
0answers
60 views

Translation/proof of elementary argument of Chebyshev

My question is whether the following proof is correct and how it might be better presented. This was an exercise to translate/shorten Chebyshev's argument that $\hspace{80mm} (1)$ $\hspace{55mm}\log ...
1
vote
0answers
48 views

Looking for an algebraic proof of an unusual equality [duplicate]

I have stumbled on the equality $[\sum i]^2 = \sum i^3$ which holds when both sums are over the range 1 to k. The equality is readily demonstrated inductively, but I wonder if anyone can provide an ...
1
vote
0answers
88 views

gcd finding method

An integer $d$ is a $\gcd$ of two non-zero integers $a$ and $b$, if $d$ divides $a$ & $d$ divides $b$ '$c$ divides $a$ & $c$ divides $b$' implies '$c$ divides $d$' for any integer $c$. If ...
1
vote
0answers
33 views

Are there infinitely many emirps? [duplicate]

An emirp is a prime number such that when its decimal digits are reversed, one obtains a different prime number. Are there infinitely many ermips? It is apparently open whether there are infinitely ...
1
vote
0answers
49 views

Specific Modular Arithmetic Question with Exponentiation

Are there any theorems that can be used to reduce $1213^{797} \pmod {2591}$ without using a computer?
1
vote
2answers
62 views

Is the quotients of a group of triangular distributed numbers still following a triangular distribution?

I have a group of numbers (about 10000 numbers) between 0.8 and 1.0 which follows simple triangular distribution (for example, lower limit: 0.8, upper limit: 1.0, mode: 0.9). If I divide 2 by each ...
1
vote
0answers
30 views

A Greatest Common Divisor Property [duplicate]

Show that: If $c|a^m-1$ and $c|a^n-1$ then $c|a^{gcd(m,n)}-1$
1
vote
0answers
66 views

When is $n!+1$ a square? [duplicate]

I'm looking for the solutions $(n,m)$ of the equation $n!+1=m^2$. I have calculated the values of $\sqrt{n!+1}$ for $n \le $ and found only the solutions $(4,5)$, $(5,11)$ and $(7,71)$. Are these ...
1
vote
0answers
50 views

How to build $\operatorname{Hom}(\mathbb{Z}_p^*,\mathbb{Z}_{pq}^*)$ without solving DLP?

For given two distinct primes p and q, I want to construct all homomorphisms from the multiplicative group $\mathbb{Z}_p^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$. Thanks to Jyrki ...
1
vote
0answers
65 views

Simplify $\frac{[m+n-1]!}{[m]![n]!}$ where $[k]=x^k-x^{-k}$ and $[k]!=[2][3]…[k]$.

Adopting the notation $[k] = x^k - x^{-k} $ and $[k]! = [2][3]...[k]$ (note that $[1]$ is omitted), and letting $m,n$ be two integers greater than $1$ such that $n>m$ and $gcd(m,n)=1$, would it be ...
1
vote
1answer
73 views

existence of a prime $p$ for which $a$ is a primitive root

It is known that every prime $p$ has a primitive root modulo $p$. Is every number $a$ which is not a perfect square a primitive root modulo $p$ for some prime $p$? If it is a square, we already have ...
1
vote
1answer
635 views

Evaluating $\sum_{i=0}^{m-1} [ \frac{b + ia}m ]$

Let $a,b\in\mathbb{Z}$ and $m\in\mathbb{Z}_{>1}$ Evaluate $[\frac {b}{m}] + [\frac {(b+a)}{m}]+ [\frac {(b+2a)}{m}]+ [\frac {(b+3a)}{m}]+ [\frac {(b+4a)}{m}]+ [\frac {(b+5a)}{m}]+.....+ [\frac ...
1
vote
0answers
199 views

Ramanujan-Nagell and Pell’s equation

In my study of Pell’s equation $(x(d))^2-d(y(d))^2=1$ (eq.1), I looked at the family of equations where $d=2^n-3$ to which 61 belongs. (This was really a study of d=61 in equation 1.) In some cases, ...
1
vote
0answers
50 views

solutions to $f(y) = n(n + 1) \ldots (n + m - 1)$

I was reading a paper about solutions to $f(y) = P(m)$, where $f(y) \in \mathbb Z[y]$ and $P(m) = n(n + 1) \ldots (n + m - 1)$ is a product of $m$ consecutive integers ...
1
vote
2answers
33 views

What is $\operatorname{max}(x)$ given that $ x \equiv n^p \pmod{q}$?

Look at this: $$ x \equiv n^p \pmod{q} $$ What is $\operatorname{max}(x)$?
1
vote
2answers
191 views

Proof that any polynomial with a positive leading coefficient is eventually positive?

The exact theorem I've been asked to prove is the following: Suppose $f(x)=a_n x^n + a_{n-1}x^{n-1} + ...+a_0$ is a polynomial of degree $n>0$ and suppose $a_n>0$. Then there is an integer $k$ ...
1
vote
1answer
136 views

Pell's equation has high solutions when d is a member of OEIS A008784

Let $x(d),\, y(d),\, d$ and $n$ be natural numbers, such that $(x(d))^2-d(y(d))^2=1$. I denote the $x$ solution $x(\textrm{dmax})$, if $x(\textrm{dmax}) > x(d)$ in the interval ...
1
vote
0answers
37 views

(probability + algebra ) in cryptography.

Suppose we know $n$ - which is a product of two unknown primes - and also an integer m such that $a^m \equiv$ 1 mod n for all a prime to n. We see that any such m must be even (as we see by taking a ...
1
vote
1answer
168 views

Modulus Cancellation Law

I'm trying to understand the proof for cancellation law in modulus which states that: ...
1
vote
1answer
71 views

Revised: Primes of form $p \equiv m \in S \mod x \ $

Refer to this question for background. I was speculating if there was an elegant way to define sequences A007645,A002313,A045357,A045407,A042986,A045331, A045425,A045374,A045400,A045350,A042988; ...
1
vote
2answers
118 views

Classify the odd primes $q$ such that a NEGATIVE number is a quadratic residue $\mod{q}$

Suppose we are given $y < -1$. I wish to classify all primes $q$ such that $y$ is a quadratic residue $\pmod{q}$, i.e. such that there exists a number $x$ satisfying $$y \equiv x^2 \pmod{q}.$$ How ...
1
vote
0answers
148 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
1
vote
1answer
117 views

How quickly can we detect if a digit is in a number?

If we suppose that we have a number $n$ in base $b$, represented as a power series: $$n = d_0 b^0 + d_1 b^1 + d_2 b^2 + \dots$$ ...where the $d_k$'s are the digits, how quickly can we determine if ...
1
vote
1answer
73 views

Looking for name of theorem: “rational $\Leftrightarrow$ fractional part terminates or repeats”

I am looking for the name of the theorem that says that a number $x$ is rational if and only if its fractional part terminates or repeats (where "fractional part" refers to the representation of $x$ ...
1
vote
1answer
382 views

Relation between sum of squared norm and squared norm of sum of vectors?

Is there a relation between $||\sum_{i=1}^n \mathbf x_i||^2$ and $\sum_{i=1}^n||\mathbf x_i||^2$ where each $\mathbf x_i \in R^N$, and $||\cdot||$ is $L_2$ norm?
1
vote
0answers
69 views

Euler product of $\frac{1}{\gamma}$

I am trying to calculate the euler product of $\frac{1}{\gamma}(n)$ where $\gamma(n)$ is the number of divisors of n. So I have that: $\displaystyle D_{\frac{1}{\gamma}(n)}=\prod_p \left ( 1+ ...
1
vote
0answers
96 views

On the elliptic curve $x^4+y^4 =193z^2$

Given the simultaneous Diophantine equations, $$u^2+v^2=w^2\tag{1}$$ $$x^4+y^4 = (u^6+v^6)t^2\tag{2}$$ the only solutions seem to be for the first Pythagorean triple $u,v,w = 3,4,5$ which yield the ...
1
vote
0answers
44 views

What are $\sigma$ and $\tau$ in $n = 2^{\sigma(n)}\,\tau(n)$ called?

Every non-zero integer $n$ can be factored uniquely as $2^s t$, where $s$ is a non-negative integer, and $t$ is an odd integer. In other words, there exist functions $\sigma:\mathbb{Z}\backslash ...
1
vote
0answers
13 views

Are there ways to get modulated values similar to cyclic and negacyclic convolutions?

The Wikipedia article on the Schönhage–Strassen algorithm states that there are methods that can get values modulo $a^n+1$ or $a^n-1$ for some value $a$. More specifically, it shows that the cyclic ...
1
vote
0answers
88 views

Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations

Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations of $p=7,11,13$ and $q=227$ My thought: $(7, 227)$ are distint odd primes, same for $(11,227)$ and $(13, 227)$ thus, ...
1
vote
1answer
77 views

Erdős–Turan construction of Golomb ruler

The following equation produces a Golomb ruler for every odd prime p $$ 2pk + (k^2 \bmod p), \quad k\in[0,p-1] $$ and every two contiguous points has a unique difference. my question is how to get ...
1
vote
0answers
119 views

Week of the problem on Diophantine equation

S.E board! This is a Diophantine equations problem, which is so interesting one can do by plugging the suitable values in unknown. When it comes for finding set of all solutions is may be tough. I ...
1
vote
1answer
63 views

If $p$ is prime, $a \in \Bbb Z$, $ord^a_p=3$. Then how to find $ord^{a+1}_p=?$

If $p$ is prime, $a \in \Bbb Z$, $ord^a_p=3$. Then how to find $ord^{a+1}_p=?$ about $ord_n^a$ we know that is $(a,n)=1$ and smallest integer number as $d$ such that $a^d \equiv 1$ so $d=ord_n^a$ ...
1
vote
0answers
37 views

Exactly $\phi(\phi(n))$ primitive roots modulo $n$ [duplicate]

If $n\in \Bbb N$ is a primitive root then how to prove that: There are exactly $\phi(\phi(n))$ primitive roots modulo $n$ such that are peer to peer $\not \equiv$