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

learn more… | top users | synonyms (1)

0
votes
3answers
236 views

Let $w, x, y, z$ be natural numbers. Find the correct alternative.

Let $w$, $x$, $y$, $z$ be four natural numbers such that their sum is $8\cdot m+10$, where $m$ is a natural number. Given $m$ which of the following is possible: The max. possible value of ...
4
votes
1answer
67 views

Fibonacci Numbers $F_n$ and $F_{n + 1}$ are relatively prime for all $n \geq 0$.

I have looked a bunch of solutions of this problem on the web. But I want to know that whether my solution is correct or not. My solution is as follows Proof(By Induction) $P(n)$:The Fibonacci ...
3
votes
4answers
126 views

$2^{2^n}+5^{2^n}+7^{2^n}$ is always divisible by $39$

This problem is really bothering me for some time, I appreciate if you have some idea and insight. Prove that $$2^{2^n}+5^{2^n}+7^{2^n}$$ is divisible by $39$ for all natural numbers ...
7
votes
2answers
148 views

At least 99% of these numbers are composite

This is from a contest preparation: Prove that at least 99% of these numbers $$10^1+1,10^2+1, 10^3+1, ..., 10^{2010}+1$$ are composite. The problem is from 2010, obviously. I was ...
6
votes
1answer
289 views

Sum of a Sequence of Prime Powers $p^{2n}+p^{2n-1}+\cdots+p+1$ is a Perfect Square

Find all primes p such that $p^{2n}+p^{2n-1}+p^{2n-2}+\cdots+p^{2}+p+1$ is a square for some value of n.
2
votes
1answer
68 views

Improving the inequality $x\sigma_1(x) \leq \sigma_1(x^2)$ for $x \in \mathbb{N}$

Let $\mathbb{N}$ be the set of positive integers. For $x \in \mathbb{N}$, $\sigma_1(x)$ gives the sum of the divisors of $x$. (For example, $\sigma_1(3) = 1 + 3 = 4$.) We call the ratio $I(x) = ...
2
votes
1answer
71 views

Does $a\in\mathbb Z$ such that $\gcd(n,a(m-a))=1$ exist for every $(m,n)\not=(\text{odd},\text{even})$?

When I was thinking about the greatest common divisors, I noticed that we seem to be able to find at least one integer $a$ such that $$\gcd(n,a(m-a))=1$$ for every pair of positive integers $(m,n)$ ...
2
votes
1answer
59 views

Find the tens place of a number

For any odd number N ending with the digits $1,3,7$ or $9$, $(N)^{20\cdot n}$ ends with $01$. Here, $n$ is any natural number Now I have tested the result with a few odd numbers. But is there any ...
0
votes
3answers
132 views

Matrices, determinants, and applications to identities involving Fibonacci numbers

Preamble It is well known that since: $$ \begin{pmatrix} F_{n+1} \\ F_n \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} F_n & F_{n-1} ...
4
votes
1answer
302 views

Comparing two definitions of a set of natural numbers

Let $n_1,n_2,N\in \mathbb{N}$. I want to show the following: The two sets \begin{align*} &\Delta(n_1,n_2,N)\\ =& \Big\{ a\cdot b: \quad a\mid {n_1}^2,~a^2 \mid {n_1}^2N ,\gcd\left(N ...
3
votes
3answers
115 views

Diophantine equation $l^2+m^2+n^2=p^3+q^3$

I'm not familiar with Diophantine equations. I would like to solve the following equation: $$l^2+m^2+n^2=p^3+q^3$$ where $l,m,n,p,q\in\mathbb{N}$. I need a list of solutions where $l^2+m^2+n^2$ < ...
5
votes
2answers
246 views

What is the coefficient of $x^{18}$ in the expansion of $(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}$?

How to approach this type of question in general? How to use binomial theorem? How to use multinomial theorem? Are there any other combinatorial arguments available to solve this type of question? ...
3
votes
4answers
114 views

Why do we have $ab=ba$? [duplicate]

Why is it that $$ab=ba$$ for positive integers $a,b$? Is there an intuitive explanation or we just need to accept it as a given fact?
2
votes
2answers
459 views

Confusion on the proof that there are “arbitrarily large gaps between successive primes”

I am trying to wrap my brain around a proof that proves that there are arbitrarily large gaps between successive primes. The proof is Given a natural number $N\ge2$, consider the sequence of $N$ ...
2
votes
3answers
39 views

Is there a general formalism for 3-variable quadratic diophantine equations without mixed terms?

Consider a polynomial equation $$P_x(x) + P_y(y) + P_z(z) = 0\tag1 $$ Where $P_x, P_y, P_z$ are polynomials of degree at most two with integer coefficients. The problem is to characterize all ...
1
vote
3answers
162 views

Why do some accept zero as a natural number but others don't? [duplicate]

I have had many teachers who have told me that zero is a natural number but then there is those teachers who say its not. why is that ?
0
votes
1answer
33 views

How to derive bounds for the $n$-th term of a subsequence of $\mathbb {N} $, knowing two functions “squeezing” the number of the terms below $x$?

Let $ a_n $ be the $n $-th term of an infinite strictly increasing subsequence of $ \mathbb{N}$ and denote with $\nu(x)$ the number of terms smaller than or equal to $x$. Assume also ...
2
votes
1answer
67 views

For every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$. I have no idea how to prove that.
1
vote
2answers
1k views

Chinese remainder theorem for non-prime / non-coprime moduli

If I want to find some number $x$ where it leaves a remainder when divided by some prime $p$, and another remainder when divided by some prime $q$, and so on, I can use the Chinese Remainder Theorem. ...
4
votes
2answers
55 views

Is inverse of Dirichlet convolution unique ?

We know that the Dirichlet inverse of the constant function 1 is the Möbius function. I just want to confirm that Möbius function is the only function which is the inverse of constant function for ...
3
votes
2answers
79 views

Prove that the Diophantine equation has only one solution for $a,b,c$.

Prove that the Diophantine equation $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1$ has only one solution for positive integers $a,b,c$ with $a<b<c$
1
vote
2answers
71 views

How can I prove this using number theory only

So this book I'm reading has this question: show that if $(a,n)=(b,n)=1$ the the equation $$ax+by\equiv c(mod( n))$$ has exactly $n$ different solutions. I was only able to prove it using ...
2
votes
1answer
49 views

Finding solutions of a 2-variable biquadratic equation

Find all integral solutions of $$y^2+y=x^4+x^3+x^2+x$$ Factoring both sides we get $$y(y+1)=(x^2+x)(x^2+1)$$ Let $Y=y+1/2$ and $X=x^2+\frac {x+1}2$. Therefore $$(Y+1/2)(Y-1/2)=(X+\frac{x-1}2)(X-\frac ...
6
votes
4answers
2k views

How many natural numbers less than 200 will have 12 factors/divisors?

How many natural numbers less than 200 will have 12 factors (a.k.a. divisors)? I think the answer is $11$. Firstly there can be at most $3$ distinct prime factors. $12=1\cdot12 =2\cdot6 ...
97
votes
11answers
6k views

Is there a domain “larger” than (i.e., a supserset of) the complex number domain?

I've been teaching my 10yo son some (for me, anyway) pretty advanced mathematics recently and he stumped me with a question. The background is this. In the domain of natural numbers, addition and ...
1
vote
2answers
71 views

A ray with initial point $0$ need to pass arbitrarily near to a integer point.

How can I prove that for a ray $\overrightarrow{0x}=\{\lambda x| \lambda \in \mathbb{R}_{\geq 0}\}$ in $\mathbb{R}^n$ we have $d(\mathbb{Z}^n \setminus \{0\},\overrightarrow{0x})=0$?
2
votes
1answer
74 views

Question about $2p-1$ and $2p+1$, where $p$ is a prime.

Let $x+1$ be any prime greater than $3$. By Bertrand's Postulate, there is at least one prime between $\frac{x}{2}$ and $x$. Let $\{p_1,p_2,\dots, p_n\}$ be the primes between $\frac{x}{2}$ and ...
2
votes
1answer
60 views

Number of squares in $(\mathbb{Z}/p\mathbb{Z})^\times$

$x$ is a square in $(\mathbb{Z} /p \mathbb{Z})^\times$ iff there is a $y \in (\mathbb{Z} /p \mathbb{Z})^\times$ such that $x \equiv y^2 \mod p$. I am asked to show that there are exactly ...
2
votes
3answers
163 views

For how many natural numbers $X(X+1)(X+2)(X+3)$ has exactly three different prime factors?

For how many natural numbers $X(X+1)(X+2)(X+3)$ has exactly three different prime factors? My attempt: I have used a hit and trial approach. I found out that only for x=2 and x=3 this is ...
3
votes
1answer
45 views

for every positive integer $n$, find $n$ consecutive numbers which are not squarefree

I want to show that for every positive integer $n$, I can find $n$ integers in a row whose prime factorization contains at least one prime twice. I checked the cases $n=2$ $(8,9)$ and $n=3$ ...
2
votes
0answers
79 views

Properties of non-equivalent solutions to the generalized Pell equation

Given the Diophantine equation $$ r^2-ds^2 = x^2-dy^2 = q, $$ (where $q$ is a potentially unknown integer, and certainly need not be $1$), the two solutions $(r,s)$ and $(x,y)$ are called equivalent ...
2
votes
1answer
79 views

finding solutions to system of congruences $x \equiv 1 \mod 2$, $2 \mod 3$, $3 \mod 5$

I want to solve the following system of congruences: $$ x \equiv 1 \mod 2\\ x \equiv 2 \mod 3\\ x \equiv 3 \mod 5$$ By checking all small numbers, I got $x=23$ as smallest solution. I think that all ...
2
votes
2answers
73 views

Seven expressions involving $F_n$ an $L_n$ that are always composite

Prove that if $F_n$ an $L_n$ are Fibonacci and Lucas numbers respectively, and $n>2$, then $$F_{n-2}\times F_{n-1}\times F_{n+1}\times F_{n+2}-15$$ $$F_{n-2}\times F_{n-1}\times ...
37
votes
5answers
6k views

If a prime number is reversed, and then appended to itself, why is the result always a composite number?

$2 \Rightarrow 22$ which is a composite number. $37 \Rightarrow 3773$ which is a composite number. $523 \Rightarrow 523325$ which is a composite number. $8123 \Rightarrow 81233218$ which is a ...
3
votes
2answers
76 views

Proving all sufficiently large integers can be written in the form $ax+by$

Let $a,b \in \mathbb N \setminus \{0,1\}$ such that $\gcd(a,b)=1$ Let $F=\{ax+by \mid (x,y) \in \mathbb N^2\}$ Prove that all integers $\geq (a-1)(b-1)$ are in $F$, but that ...
3
votes
2answers
242 views

find x where $x^{11} \mod 41 = 10$

In a previous part of the question, I am asked to find $11^{-1} \mod 40$. I've done that, the answer's $11$. The question continues: find $x$ where $x^{11} \mod 41 = 10$ showing how you could get ...
3
votes
3answers
185 views

Finding value of 1 variable in a 3-variable $2^{nd}$ degree equation

The question is: If $a,b,\space (a^2+b^2)/(ab-1)=q$ are positive integers, then prove that $q=5$. Also prove that for $q=5$ there are infinitely many solutions in $\mathbf N$ for $a$ and $b$. I ...
2
votes
0answers
51 views

Can we recover a number from the values of Mobius function?

All: We are considering a question. If we know the values of Mobius function for all numbers less than $n$, can we recover $n$ from all of those Mobius function values? Essentially, we want to know ...
2
votes
3answers
139 views

Is a prime to the power of a fraction always irrational?

Let $p$ be a prime number and let $x$ be a fraction, i.e. $x \in \mathbb{Q} \setminus \mathbb{N}$. It seems to be the case that $p^x$ is always irrational. How do I prove this?
2
votes
2answers
117 views

Find the smallest natural number that can not be written as a sum of elements of S?

Given a set of natural numbers $S_1$ , $S$ and a number N . Specification of sets are as follow . $$S = \{1,\dots N\}$$ $$S_1\subset S \;and \;S_1=\{b_1,b_2,\dots,b_m\}$$ And $$S' = S\setminus ...
2
votes
1answer
122 views

What is the next composite number?

If $p_n$ is the nth prime number. then what is the next composite number after say $p_4^2\times p_5$ without actual calculation? ($p_4^2\times p_5+1$ is $p_1^2p_2^3p_3$) the first few composite ...
1
vote
0answers
44 views

Proof for solving linear congruence

Show that the equation $$ a x \equiv b \bmod{n} \; \quad a, b \in \mathbb{Z}\, , n \in \mathbb{N} $$ with $d:= \gcd(a,n)$ has no solution if $d \nmid b$. But if $d \mid b$, it is equivalent to $$ ...
2
votes
3answers
295 views

When is $(x-1)(y-1)(z-1)$ a factor of $xyz-1$?

Let $x$, $y$, $z$ be three natural numbers such that $1< x< y< z$. For how many sets of values of $(x,y,z)$, is $(x-1)(y-1)(z-1)$ a factor of $xyz-1$? I noticed that ...
3
votes
1answer
90 views

Find the number of natural numbers

$N$ is a natural number greater than 1 and less than 100. $F(1), F(2), \dots, F(n)$ are the factors of $N$ in such a way that $1=F(1)< F(2)< F(3)< \dots < F(n)=N$. Further, $D= ...
4
votes
2answers
56 views

Find integer solution to the given system of equation.

find all positive integers $a,b,c$ such that $abc=24$ $ab+bc+ca=38$ If particular values are given then we can easily find the solution but I am searching for some short general method. Is there ...
3
votes
3answers
147 views

Proof that the product of primitive Pythagorean hypotenuses is also a primitive Pythagorean hypotenuse

Just to be clear, I call an integer $c$ a 'primitive Pythagorean hypotenuse' if there exist coprime integers $a$ and $b$ satisfying $a^2+b^2 = c^2$. I noticed that the set of such primitive ...
7
votes
1answer
134 views

Is there a better way to factor $375007$ with out testing first $612$ primes? No calculators please

Is there a better way to factor $375007$ with out testing first $612$ primes ? I know this factors to $31\times 12097$ by testing the primes $2,3,5,\ldots,31$. Is there any other clever way to ...
1
vote
2answers
78 views

Solve $x^5 - x = 0$ mod $4$ and mod $5$

I'm trying to solve $$x^5-x=0$$ in $\mathbb{Z/5Z}$ and $\mathbb{Z/4Z}$ I don't see how to proceed, could you tell me how ? Thank you
3
votes
1answer
92 views

A subset of size $101$ from $1, 2, 3, \ldots, 200$ must contain one element which divides another

Let $A$ be a subset of size 101 from the set $\{$1, 2, 3, . . . , 200$\}$ (of size 200). Show that $A$ contains an $x$ and a $y$ such that $x$ divides $y$. This seems like it has something to do ...
7
votes
1answer
149 views

Prove or disprove that ${F_{n}}^2 + 41$ is always a composite

The problem: Prove or disprove: If $F_{n}$ is the $n^{th}$ Fibonacci number then $${F_{n}}^2 + 41$$ is always a composite number. It looks that if $n$ is not multiple of 12, ${F_{n}}^2 + 41$ ...