# Tagged Questions

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

244 views

### Does the sequence $q(n)=3n+1+\frac{1-(-1)^n}{2}$ generate all the prime numbers?

Define $$q(n)=3n+1+\frac{1-(-1)^n}{2} \quad, \quad n\in \mathbb N.$$ $$1,5,7,11,13,17,19,23,25,29,31,35,\dots$$ It seems like this formula gives all primes $>3$ (although not just primes of ...
39 views

### Taking averages of averages

The numbers $1000$ and $1000000$ are already written on a paper. We are allowed to write down an average of two written numbers, if that average is an integer has not been written before, and we can ...
30 views

### For which $0\leq a<p^2$, where $p$ is an odd prime, we have that $(2p-1)!\equiv a\mod{p^2}$

Let $p$ be an odd prime. I need to find for which $0\leq a < p^2$, $(2p-1)!\equiv a\mod{p^2}$. If $a\equiv (2p-1)!\mod{p^2}$, then we have that $a = kp^2 + (2p-1)!$, and therefore $p\mid a$, ...
81 views

### Discrete logarithm modulo powers of a small prime

Is there an efficient way to compute $x$ in $2^x \equiv b \pmod {p^m}$, where $p$ is a small odd prime and $m$ could be a large integer? I know the solution is of the form $x=\phi(p^m) k + y$ for ...
27 views

### Sum of fractional parts in $(1,2)$

Let $a,b,c$ be any rational, non-integer positive numbers with non-integer sum. Does there always exist a positive integer $k$ such that $ka,kb,kc$ are not integers and $\{ka\}+\{kb\}+\{kc\}\in(1,2)$? ...
19 views

### Return a cross product of two sets A and B such that only one entry is returned based on a condition

Lets say I have a set $A={\text{'Akshat'},\text{'John'},\text{'Mike'}}$ and a set $B={\text{'Modi'},\text{'Kerry'}}$. Set $A$ represents a set of voters while $B$ represents a set of candidates for an ...
68 views

### Find the number of sums that you will get A, when A=100?

Problem: Take any number $A \in \Bbb{N} = \{1, 2, 3, \dots\}$, and then take $x, y \in \Bbb{N}$, where $x \ne y$ and $x + y = A$. Find the number of possible choices for $x$ and $y$ when $A=100$. ...
42 views

### Show that for $x,y,z\in\mathbb{Z}$, if $x$ and $y$ are coprime, then $\exists n\in\mathbb{Z}$ such that $z$ and $y+xn$ are coprime.

Not sure where to start on this one. I understand that coprime indicates that their GCD is 1, but I am somewhat confused how to proceed.
24 views

### On some iterated inequalities and $x \geq 5$

Let $x \in \mathbb{N}$. Suppose that I have a function $f:\mathbb{N}\rightarrow\mathbb{Q}$, with initial bounds $$2 - \frac{2}{x_0} < f(x_0) = \frac{2{x_0}}{x_0 + 1} \leq 2 - \frac{5}{3x_0}.$$ ...
30 views

### A simple inequality in number theory

If $0 < a,b,c <1$, then is the following inequality true?$$a^2(b+c)+b^2(c+a)+c^2(a+b)+ab+bc+ca-a-b-c \ge0$$
45 views

### An unexplained condition on $a$ in a proof on the primes?

Lemma A positive integer $n$ is a prime if $(n,p) = 1$ for every prime integer $p \leq \sqrt{n}$ Proof in my text Let $(n,p) = 1$ for every prime $p \leq \sqrt{n} \:$. Suppose $n$ is not a ...
46 views

### $(a+b-c)(b+c-a)(c+a-b)$ divides $abc$

Do there exist pairwise distinct positive integers $a,b,c,d$ such that no two sum to another, and $(a+b-c)(b+c-a)(c+a-b)$ divides $abc$ $(a+b-d)(b+d-a)(d+a-b)$ divides $abd$? If we only require ...
15 views

### number of days it takes to visit all the locations in matrix

The seats in a classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right). After every day ,we are allowed to move ...
70 views

65 views

### Need help with proof about Diophantine equations

The way I am planning to arrange this is by providing fragments of the proof, so I can understand what's going on before forging ahead, so if you are going to help me, keep in mind that I am going to ...
112 views

54 views

### Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$.

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$. I'm having a difficult time proving this problem. I was able to verify that it works for prime $n$ up to ...
45 views

### Progressions modulo $n$

I don't understand how to do these 2 tasks: 1) Prove that any arithmetic progression modulo $n$ has a period that divides $n$. 2) Prove that any geometric progression modulo a prime number $p$ has a ...
If $m = a_1x + b_1y$ , $n = a_2x + b_2y$ , $a_1b_2 - a_2b_1 = 1$ then prove that $\gcd (m,n) = \gcd (x, y)$ My attempt Let $c = \gcd (x,y)$ and $d = \gcd (m,n)$ then $c \mid d$ $\frac{d}{c} = \... 2answers 84 views ### The$25$th digit of$100!$I want to find The$25$th digit of$100!$. My attempt:It is easy to know it has$24$zeroes.Because:$\lfloor {\frac{100}{5}} \rfloor+\lfloor {\frac{100}{25}} \rfloor =24$By getting the fist ... 4answers 2k views ### Have I found all the numbers less than 50,000 with exactly 11 divisors? The math problem I am trying to solve is to find all positive integers that meet these two conditions: have exactly 11 divisors are less than 50,000 My starting point is a number with exactly 11 ... 0answers 140 views ### Are all theorems usable? [closed] The (revised) question to answer: Can anyone give an example of a serious proof using this funny (revised) theorem? For any natural number$n$and prime$p<n-1$there exist a prime$q$... 3answers 79 views ### There exists infinitely many$n\in\mathbb{Z}$such that$f(n)$is a prime. I found in a number theory book the following lines Let$f(x)$be a non-constant polynomial with integer coefficients such that none of the following hold for it 1) There is an integer$d>1$... 1answer 32 views ### The greatest common divisor of$(O_n, T_n+2)$where$O_n$and$T_n$are the oblong and triangular numbers respectively. Suppose that$T_n$is odd. Can we find infinitely many$n$such that$(O_n, T_n+2)=1$? Is it trivial and obvious? My hunch based on some hand calculations is to look at$n$congruent to$0$or$2$... 3answers 63 views ### Prove that there are exactly$k$pairs$(x,y)$of rational numbers with$0\leq x,y<1$for which both$ax+by,cx+dy$are integers. Let$a,b,c,d$are integers such that$(a,b)=(c,d)=1$and$ad-bc=k>0$. Prove that there are exactly$k$pairs$(x,y)$of rational numbers with$0\leq x,y<1$for which both$ax+by,cx+dy$are ... 1answer 20 views ### Arithmetic mean of the integers in set$S=\{k:k\in \mathbb{Z}, 1\leq k\leq n$and$gcd(k,n)=1\}$Or stated simply, what is the arithmetic mean of the totatives of$n$? From this question here I can see that the sum of the totatives is given by the formula$\large\frac{n\times\phi (n)}{2}\large$. ... 2answers 125 views ### How does$x^4+y^4=z^2 \implies x^4+y^4=z^4$? Why is the statement "the following cannot be satisfied" for$x^4+y^4=z^2$more strong than for$x^4+y^4=z^4?$More specifically, how does$x^4+y^4=z^2 \implies x^4+y^4=z^4?$This statement was ... 0answers 91 views ### Is a finite number of quadratic equations in two variables sufficient to solve for the two variables? Let's say I’m trying to solve a Diophantine problem in two positive integers,$y$and$q$. Furthermore, let’s say I can derive an extremely large (read: arbitrary) number of equations of the form $$ay^... 1answer 39 views ### Statement regarding primes \le n Following is the statement I believe is true, but can't prove. Let n be a natural. Let the primes less than equal to \sqrt{n} be p_1,p_2,...,p_k. Let \alpha_i be the greatest natural ... 0answers 62 views ### Algebraic number that exponentiated with algebraic number give \pi I'm not sure if an algebraic number elevated with an algebraic exponent can give rise to a transcendental number. If that's the case does anybody know a closed form for an algebraic number that ... 5answers 88 views ### Find all natural numbers n such that n^{17}-n is divisible by 10 I've encountered this math problem and I don't know how to solve it. What math region,field(however you call it. English is not my first language) is used here ? Find all natural numbers for which ... 1answer 35 views ### No prime between these two numbers For a fixed k\in \Bbb N, why is there no prime number between (k+2)!+2 and (k+2)!+2+k? My professor said this but didn't prove it. 0answers 49 views ### Intersection of two sets of rationals I'm looking to see if anyone has any solutions or references for this problem. I'm not even sure of a proper category. It seems like it should be trivial, perhaps I'm missing something obvious. ... 0answers 58 views ### A function can provide the complete set of Euler primes via a Mill's-like constant. Is it useful or just a curiosity? The following f(m,n) function provides the complete set of Euler primes (OEIS A196230):$$f(m,n)=m^2-m+[\lfloor E^{2^n} \rfloor - {\lfloor E^{2^{n-1}} \rfloor}^2 +\frac{\lvert n-(\frac{1}{2}) \... 2answers 42 views ### Relation between HCF, LCM and product of multiple numbers [duplicate] It is well known that for two numbers$a $and$b$, $$\text {lcm} (a,b)\times \text {hcf} (a,b)=ab$$ Does there exist a similar equality/ inequality between HCF, LCM and product of multiple numbers? (... 1answer 106 views ### Prove that$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$is an integer Let$a$and$b$be integers and$n$a positive integer. Prove that $$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$$ is an integer. Define$v_p(x)$such that if$v_p(x) = n$, then$p^n \mid x$but ... 1answer 48 views ### Help on an application of Dirichlet's theorem for primes in progression Suppose that I have an infinite sequence of positive integers $$a_1,\ldots,a_m,\ldots$$ with the following recursion $$a_{m+1} -a_m =b(m+1)$$ So that $$a_{m+1} =b(m+1) +a_m$$ Suppose ... 0answers 15 views ### Steep Diagonals and Magic Squares We want to describe via a picture a set of subsets of a square which are something like diagonals, but are not quite the same. We’ll call them steep diagonals. One of them, labelled e, is illustrated ... 2answers 31 views ### Positive integer solution$pm = qn+1$Let$m,n$be relatively prime positive integers. Prove that there exist positive integers$p,q$such that$pm = qn+1$. We know Bézout's identity that there exist integers$p,q$such that$pm+qn = 1$,... 0answers 20 views ### Solving a system of congruences with unkown moduli? So I have two congruences of the form: n[1]=r[1] mod m and n[2]=r[2] mod (a*m+b) with known n,r,a, and b. Is there a way way to efficiently get (an acceptable) m? Edit: I mean is there any way ... 2answers 45 views ### How many integer solutions for$a = n(4m-1)/4b$? For the equation $$a = \frac{n(4m-1)}{4b}$$ where$n,m,a$and$b$are positive integers and$1\leq a,b\leq n$, how many valid, unique solutions$(a,m)$exist for fixed$n$... 2answers 117 views ### Primes in the binomial transform of$ [1, 1, 2, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, …]$. This question is related to this sequence A139482. A commentator gives the following formula for$a_m$$$a_m = {3m^2-9m+10 \above 1.5pt 2}$$ I have that you should consider the sequence$b_n =3n+2$... 7answers 921 views ### Find all even numbers that can be represented as a difference of squares in only two ways I am currently working on this proof. I am looking to find (with proof) all even numbers that can be represented as a difference of squares in only two ways. My thoughts thus far. I examined the ... 1answer 33 views ### Chartrand Mathematical Proofs 3e Exercise 5.22 I am self-studying this book, and have got stuck on this question: 5.22 Let$S=\left\{ p+q\sqrt{2}:p,q\in\mathbb{Q}\right\}$,$T=\left\{ r+s\sqrt{3}:r,s\in\mathbb{Q}\right\}$. Prove that$S\cap ...
What is the relative density of the prime numbers among the set of prime powers? In particular, let $\Pi(x)$ be the number of prime powers less than $x$ and let $\pi(x)$ be the number of primes less ...