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

learn more… | top users | synonyms (1)

7
votes
1answer
286 views

Sum of product with primes

Let $b=e_1e_2,\ldots,e_n$ and $b'=e'_1e'_2,\ldots,e'_n$ be two distinct bit strings of equal length $n$ with same number of occurrences of zeros and ones. The bit string $b$ and $b'$ also must have ...
1
vote
0answers
42 views

Number theory problem of finding prime values p and q [duplicate]

Find all pairs of prime numbers $(p,q)$ such that $$p^3-q^5=(p+q)^2$$
2
votes
2answers
44 views

Show that the number of solutions of $x^2 \equiv 1 \pmod n$ is 2

let $3 \le n \in N$ for which there exists a primitive root modulo n. Show that the number of solutions of $x^2 \equiv 1 \pmod n$ is 2 what it tried - i tried showing x and 1 as the primitive root ...
3
votes
3answers
107 views

Identity on Fibonacci numbers: $F_{2n}^2=F_{2n+2}F_{2n-2}+1$?

Let $F_n$ be the Fibonacci Sequence ($F_1=F_2=1, F_{n+2}=F_{n+1}+F_{n}$). Prove that $F_{2n}^2=F_{2n+2}F_{2n-2}+1$. I've tried everything from induction to telescoping series but I haven't got close. ...
0
votes
1answer
39 views

How do raising bases to exponents work?(Basic NumberTheory Question)

I have a question here that, because I don't understand a part of it, I don't have any work. Sorry. "Let $B$ be a base that is greater than $50^{50}$, and let $N = (11_B)^{50}$. Let $X$ be the third ...
1
vote
2answers
41 views

Another (in)dependence over the nonzero rationals question

About one hour ago I asked a question which at first sight looked non-trivial to me but it is really trivial. Shame on me, whether I want it or not. Now I have, solely for fun, another question which ...
1
vote
0answers
17 views

Example of binary GCD for complex integers?

I know you can use bit shifting to speed up the GCD algorithm for a pair of integers. Is there a way to apply this idea to gaussian integers?
0
votes
1answer
26 views

Linear (in)dependence of roots over the nonzero rational numbers

I was reading some question on this site and stream of thought led me to the creation of another question that could be trivial for someone but I am unable even to start solving it. I wanna share this ...
0
votes
2answers
39 views

If $a, b\in\mathbb Z$ and $b>0,$ then there exist unique $q, r\in\mathbb Z$ such that $a=bq+r$ and $-\frac{b}{2}<r\leq\frac{b}{2}$

a friend told me about the following problem, but I have no idea how to solve it: Let $a$ and $b$ be integers, with $b>0.$ Prove that there exist unique $q$ and $r$ integers such that ...
4
votes
5answers
68 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
2
votes
3answers
51 views

the product of an odd perfect number and some even perfect number is perfect

If $a$ were an odd perfect number ,does there exist an even perfect number $b$ such that $ab$ is a perfect number?
1
vote
0answers
15 views

Generalized Bezout's Identity, subjected to a constraint on coefficients

I would like to know if there exists any good methods that can determine the following class of problems: Suppose there exists $n$ given positive integers $y_1, y_2, \dots, y_n$ and positive integers ...
2
votes
2answers
70 views

Proof to a property of Euler's totient function

The property is $$\sum_{d|n}\phi(d) = n$$ And the proof provided is If $d$ divides $n$, let $C_d$ be the unique subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d$, and let $\Phi_d$ be the set of ...
3
votes
0answers
61 views

'Randomness' of inverses of $(\mathbb{Z}/p \mathbb{Z})^\times$

Suppose you are given the group $(\mathbb{Z} / p \mathbb{Z})^{\times}$, where $p$ is prime. Let $A_p$ denote the sequence whose $j$th element is the inverse of $[j]$. For instance, if $p = 7$, the ...
1
vote
1answer
29 views

convergence of a “nice ” subseries of a divergent series

$$S_0 := a_1+a_2+a_3+\cdots$$ is a divergent series of positive terms whose limit approaches 0. Obtain a subseries $$S_1 := b_1+b_2+b_3+\cdots$$ from $S_0$ by deleting all terms with even subscripts. ...
0
votes
2answers
27 views

Perfect and prime numbers [closed]

Are there any perfect numbers of the form $p\times q$ , where $p$ and $q$ are different prime numbers? To answer it write an equation following your definition of perfect numbers and solve it. ...
2
votes
2answers
40 views

Euclidean Algorithm [closed]

The Euclidean Algorithm is based on the move from a pair $(m,n)$, where $m>n$, to the pair $(m-n,n)$ which is then ordered so that the larger number is listed first. If we start from two numbers ...
0
votes
0answers
53 views

How to find the number of subsets of a set $X$ such as the sum of their elements is divisible by 3?

Let $X$ be a set with $N$ numbers ($N$ is less than 1000). The problem is to find the number of subsets of $X$ such that the sum of their elements is divisible by 3. Lets denote this number by ...
8
votes
4answers
354 views

Find the sum of reciprocals of divisors given the sum of divisors

Let $d_1, d_2, \cdots d_k$ be all the factors of a positive integer '$n$' including $1$ and $n$. Suppose $d_1 + d_2 + d_3+\cdots+d_k = 72$. Then find the value of $\frac{1}{d_1}+\frac{1}{d_2}+\cdots + ...
0
votes
1answer
43 views

$\frac{(-1)^n}{2\cdot 4\cdot \cdot\cdot2n}=\frac{(-1)^n}{2^n\cdot n!}$

$$\frac{(-1)^n}{2\cdot 4\cdot \cdot\cdot2n}=\frac{(-1)^n}{2^n\cdot n!}$$ $$\frac{(-1)^n}{3\cdot 5\cdot \cdot \cdot(2n+1)}=\frac{{(-2)^n} \cdot n! }{(2n+1)!}$$ can anyone tell me if these are true or ...
3
votes
2answers
50 views

Proving that an equation has no solution in the set of integers.

I want to show that $m^3+14n^3 = 12$ has no solution in the set of integers. Could anyone provide any insight on how to do this? Thanks.
0
votes
1answer
73 views

If $(a , b , c)$ is a Pythagorean triple, then so is $(ka , kb , kc)$ [closed]

From trigonometry text: Show that if $(a , b , c)$ is a Pythagorean triple then so is $(ka , kb , kc)$ for any integer $k > 0$. How would you interpret this geometrically? Can someone please ...
2
votes
2answers
127 views

Why is ${n\choose k}$ is always a product of the primes of $n$ for all $n>k$? [closed]

Let $n, k$ be two positive integers such that $n>k$. Why is ${n\choose k}$ always divisible by a prime dividing $n$ (or even a product of such primes)? Please help me understand why. I cannot seem ...
6
votes
0answers
69 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
3
votes
1answer
41 views

Solve $7^x \equiv 6 \pmod{17}$ given 3 is a primitive root $\bmod 17$

It's easy to show that 3 is a primitive root $\bmod 17$, but how do I use it prove the congruence? Is there a general way to solve any congruence of the form $a^x \equiv b \pmod{c}$ if you know a ...
2
votes
4answers
64 views

Understanding Primitive roots

I am trying to find a single primitive root modulo $11$. The definition in my textbook says "Let $a$ and $n$ be relatively prime integers with ($a \neq 0$) and $n$ positive. Then the least ...
0
votes
2answers
46 views

Determining whether there exists an integer $a$ such that $\text{ord}_{20}(a) = 8$.

I am trying to determine whether there exists an integer $a$ such that $\text{ord}_{20}(a) = 8$. I know that if $(a,n) = 1$ and $n>0$, then $\text{ord}_{n}(a)\mid \phi(n)$. I cannot use any ...
0
votes
1answer
49 views

Is this a valid equivalent expression of the twin prime conjecture?

The twin prime conjecture states that it is possible to find two primes $p$, $p+2$ at a distance $2$ that are as big as wanted (Wikipedia). I am learning about the basic properties associated to the ...
3
votes
0answers
18 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
4
votes
5answers
57 views

Prove the digital root of a square can be anything other than $2, 3, 5, 6, 8$?

The digital root is the sum of the digits, unless that has more than one digit, so then you add up the digits again, until arriving at a single digit, e.g., $28$ -> $2 + 8 = 10$ -> $1 + 0 = 1$. For ...
0
votes
4answers
38 views

Determining whether there exists an $a$ such that $\text{ord}_{17}(a) = 4$.

I am trying to determine whether there exists an $a$ such that $\text{ord}_{17}(a) = 4$, where $\text{ord}_{17}(a)$ is the least integer $k$ such that $a^k \equiv 1\pmod{\! 17}$. This is equivalent to ...
1
vote
1answer
43 views

Average patients waiting time in dental office

At a Dental Office, patients come in at the rate of 20 per hour and, on average, are processed at the same rate. Patients wait in a queue till they are called up to the counter for registration. After ...
3
votes
1answer
44 views

If $a^p+b^q+c^r=a^q+b^r+c^p=a^r+b^p+c^q$ .prove that $ a=b=c$ or $p=q=r$?

Let $$a,b,c,p,q,r$$ be positive integers such that : $$a^p+b^q+c^r=a^q+b^r+c^p=a^r+b^p+c^q$$ How do I prove :$ a=b=c$ or $p=q=r$ ? Thank you for any kind of help.
3
votes
1answer
57 views

Is there $\phi(n)=n/6$

I know how to find for which $n$ $\phi(n)=n/2$ or $\phi(n)=n/3$, my method for finding those was simply to find primes $p$ that satisfy $\Pi_p$$_|$$_n$$1-1/p$ $ = 1/2$ or $1/3$. However, I don't ...
2
votes
0answers
90 views

Subsequence and integers as a sum of $\frac{1}{n}$

For all $M \in \mathbb{Z}$, is there a finite sequence of positive integers $(n_i)_{i \in I}$, s.t. $\sum_{i \in I} \frac{1}{n_i} = M$, and there is no subsequence $(n_i)_{i \in J}$ of $(n_i)_{i \in ...
6
votes
2answers
92 views

Alternative way to count the number of solutions to the equation $x^2 + y^2 = -1$ over $\Bbb Z /p$

$x^2 + y^2 = -1$ is a weird equation because it has no solutions over $\Bbb R$. I want to count the number of solutions it has over $\Bbb Z / p$ where $p$ is prime. If $p = 2$ then it has $p$ ...
1
vote
2answers
44 views

Solving a quadratic relation mod $13$

Solve for $x$ in $x^2 +2x +1\equiv 2 \pmod{13}$ I started with $2^{12}\equiv 1 \pmod{13}$ by Fermat's Little Theorem. I found no square root of $2$ from $(x+1)^2\equiv 2 \pmod{13}$ using a ...
2
votes
1answer
60 views

Show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ [duplicate]

Let $x_1,...,x_n$ be a natural numbers, show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$ I know $\prod \left(x_i-x_j\right)$ is the result of ...
19
votes
13answers
5k views

What is a negative number?

I'm trying to get to an abstract definition of a negative number that would fit in with the basic concept of addition/subtraction. There are questions here about multiplying and dividing negative ...
0
votes
1answer
27 views

Can a set of data have multiple medians?

I'm looking at a probability distribution where the cumulative probability distribution for a random variable $X_2$ is exactly 0.5. Does this mean that the distribution has multiple medians?
1
vote
1answer
32 views

What's the remainder when $100!+5400$ is divided by $124$?

I'm pretty much stuck on this one because of the factorial. In this case, how can I solve it?
2
votes
3answers
88 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
2
votes
5answers
111 views

Prove that if $n^2$ is odd then $n$ is odd?

Here is my solution: I assume $n^2$ is odd then I put $n^2$= $(2x-1)^2$, now I am taking root square for both sides: $\sqrt{(n^2)}$ = $\sqrt{(2x-1)^2}$ $\Rightarrow$ $n = (2x-1)$ $\Rightarrow$ $n$ is ...
1
vote
2answers
38 views

When $\pi(x) \leqslant 0.4x +1$?

It is claimed here (Lemma 2.2) that $\pi(x) \leqslant 0.4x +1$ when $x\geqslant 7.5$. Is it really so? I am very confused about the proof. Here $\pi(x)$ is the number of primes that do not exceed ...
0
votes
1answer
68 views

Foolproof primality test

I just happened to hear about a prime number test which works 100% of the cases in an university lesson about cryptography. It should be something like: if $p$ divides every coefficient of ...
12
votes
1answer
207 views

Decimal/hex palindromes: why multiples of 53?

A previous question (371 = 0x173 (Decimal/hexidecimal palindromes?)) described numbers whose decimal and hex representations are reversed of each other. Other than the trivial one-digit numbers, ...
1
vote
1answer
38 views

How to describe $\#\{0\leq x<n:\gcd(x,n) \text{ is prime}\}$ the primes in $\mathbb{Z}/(n)$.

The above set actually comes from the following: In $\mathbb{Z}/(n)$ an ideal is prime if it is generated by an element $x$ such that for the integer representative $x$ we have $\gcd(x,n)=p$. To see ...
1
vote
3answers
51 views

Solutions of $y^2 = \alpha$ in $\mathbb{F}_{19}$

So I'm working on an exercise for elliptic curves and in one of my steps I have to determine all numbers $y \in \mathbb{F}_{19}$ for which it holds that $y^2 = \alpha$, with $\alpha \in ...
1
vote
3answers
101 views

every real number has exactly one integer part

I am self studying book Analysis I by Tao, there is an exercise on proving: Exercise 5.4.3: for every real number x, there is exactly one integer N such that $$N \leq x \lt N+1$$ Can anyone give ...
-1
votes
1answer
34 views

If $\gcd(a,4)=\gcd(b,4)=2$, find $\gcd(a+b,4)$.

If the greatest common divisor (GCD) of $a$ and $4$ is $2$, and that of $b$ and $4$ is $2$, what is the GCD of $a+b$ and $4$? I tried writing $4$ as $2^2$. So GCD of $a$ and $2^2$ is $2$ and GCD of ...