Questions tagged [divisibility]

This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

Filter by
Sorted by
Tagged with
5
votes
3answers
74 views

If $a\mid b$ and $a>0$ then $(a,b)=a$

Now let $d=(a,b)$. So $d=ax+by$. Since $a\mid b$ , so we have $aq=b$, where $q \in \mathbb{Z}$. so we have $d=ax+aqy$. since a divides R.H.S , so it must divide L.H.S. So $a\mid d$ Also $d\mid a$ as ...
0
votes
3answers
891 views

Bit representation and divisibility by 3

I was reading about how to know if a number is divisible by 3 given binary representation of the number. After googling a bit I read a statement and I am puzzled how is this correct. we have to ...
14
votes
0answers
116 views

Given a positive integer $t$ does there always exist a natural number $k$ such that $(k!)^2$ is a factor of $(2k-t)!$?

For all natural numbers $k$ the ratio $$ \frac{(2k)!}{(k!)^2}=\binom{2k}k $$ is an integer. From staring at the Pascal triangle long and hard, we know that these ratios grow rather quickly as $k$ ...
4
votes
3answers
404 views

Some Pythagorean triples proofs

I'm studying about number theory by myself. So I'm sorry if the question seems to be unclear. I just want to know how to prove that one member of a Pythagorean triple is always divisible by 5 and ...
3
votes
1answer
90 views

Find all positive integers which are representable uniquely as $\frac{x^2+y}{xy+1}$ with $x,y$ positive integers.

$\textbf{Question:}$ Find all positive integers,which are representable uniquely as $$\frac{x^2+y}{xy+1}\,,$$ where $x$ and $y$ are positive integers. I think this question maybe has something to do ...
1
vote
0answers
37 views

Is this a valid proof for checking if a number K is dividable by 11,

let s = $a_{0}+a_{1}+......+a_{n}$ let k = $a_{0}+a_{1}*10^{1}+......+a_{n}*10^{n}$ k-s = $a_{1}*(9_{1})+a_{2}*(9_{1}9_{2})+......+a_{n}*(9_{1}9_{2}....9_{n})$ It is obvious that 11 will divide any ...
2
votes
1answer
67 views

Find smallest $x$ such that $\gcd(a + x, b + x) = c$.

I need to find the smallest $x$ such that $$\gcd(a + x, b + x) = c$$ where $a, b, c, x$ are positive integers and $a \le b$. I was able to rewrite it as $$\gcd(a + x, b - a) = c$$ This shows that $c$ ...
40
votes
7answers
37k views

The product of $n$ consecutive integers is divisible by $n$ factorial

How can we prove that the product of $n$ consecutive integers is divisible by $n$ factorial? Note: In this subsequent question and the comments here the OP has clarified that he seeks a proof that "...
0
votes
2answers
57 views

Proof of the Division Theorem (for all $a \in Z, b\in Z^+$, there exists $q,r\in Z$ such that $a=bq+r$ and $0\leq r\lt b$)

I've been asked to prove the division theorem (for all $a \in Z, b\in Z^+$, there exists $q,r\in Z$ such that $a=bq+r$ and $0\leq r <b$). There are many proofs on SE, and the web, however I have ...
0
votes
2answers
34 views

Divisibility Problem from an Olympiad Book

In a practice problem set of the Olumpiad book that I am solving, the following question has me stumped. $$\text{Prove that }3(7^{200}+7^{202}+7^{204})+7(3^{200}+3^{204}) -210 \text{ is divisible by ...
1
vote
3answers
126 views

A positive integer has $1001$ digits all of which are $1$'s. When this number is divided by $1001$ find the remainder

A positive integer has $1001$ digits all of which are $1$'s. When this number is divided by $1001$ find the remainder. I tried to think on it but couldn't get through. Please help.
1
vote
2answers
69 views

Show there are infinitely many natural numbers $n$ such that $n$ divides $16^n-1$ [closed]

Show there exist infinitely many natural numbers $n$ such that $n\mid 16^n-1$.
6
votes
5answers
150 views

Proving that 2 out of every 3 triangular numbers are divisible by 3

I am trying to prove the observation that the sequence of triangular numbers are divisible in the repeating pattern of not-divisible, divisible and divisible. I've never done proofs before and I'm ...
3
votes
1answer
123 views

Relationship between primes, right triangles and homogeneous polynomials

It is known that if $x^2 + y^2 = z^2$ is a primitive Pythagorean triplet then $z$ is not divisible by any prime of the form $4k-1$. The following is a generalization of this classical result which ...
13
votes
14answers
4k views

How to prove that $k^3+3k^2+2k$ is always divisible by $3$? [closed]

How can I prove that the following polynomial expression is divisible by 3 for all integers $k$? $$k^3 + 3k^2 + 2k$$
4
votes
0answers
60 views

Show that for all $n$ there exist some $n$-digit number with no $0$ in it whose digit sum divides it.

$\textbf{Question:}$Prove that for each positive integer $n$, there exists a positive integer with the following properties: • it has exactly $n$ digits, • none of the digits is $0$, • it is divisible ...
0
votes
1answer
25 views

How many numbers between 1 and 1,000 (both inclusive) are divisible by at least one of the prime between 1 to 50? How can I find this? [closed]

I was trying to solve a compettive programming problem in which constraints are so high so I want to deduce a formula for it so that i could do it for other ranges as well.
0
votes
1answer
40 views

Prove that $q$ divides (${}_q \mathrm{C}_x$) where $q$ is an odd prime and $x \in \Bbb{Z}$ is such that $1\lt x \lt q$. [duplicate]

I believe I need to show that $\frac{q!}{x!(q-x)!} = aq $ where $a\in \mathbb{Z}$ How can I show this?
0
votes
4answers
84 views
2
votes
0answers
51 views

Number of positive integers $\leq999$ such that power of $3$ in its prime factorization is odd.

Problem Let $1\leq d\leq999$ be an integer such that in the prime factorization of $d$ power of the prime $3$ is odd. Find the number of all possible such $d$. I have taken a path to find this, ...
1
vote
2answers
124 views

In the Fibonacci sequence, show that $5\mid u_m\Longleftrightarrow 5\mid m$

Knowing in the Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In the Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Proof: $\Longrightarrow$ In the ...
6
votes
1answer
89 views

If $ 1+ \frac{1}{2}+\frac{1}{3}+…+\frac{1}{100}=\frac{A}{B}$ where $A$ and $B$ are coprime positive integers, then $5\nmid A$ and $5\nmid B$.

Let the sum $$1+ \frac{1}{2}+\frac{1}{3}+.....+\frac{1}{100}=\frac{A}{B}$$ where $A,B\in \mathbb{N}$ and $\gcd(A,B)=1$. Show that neither $A $ nor $B $ is divisible by $5$. My attempt: $$\begin{...
0
votes
1answer
55 views

Prove the statements.

Prove that, f(x)=0 when k is not prime f(x)=1 when k is prime N.B: Here f(x)= a mod k means the reminder we get by dividing 'a' by 'k' I found that the statements are right by testing those. But I ...
1
vote
3answers
102 views

Prove that for any positive integer $a,$ $a^{561} \equiv a \pmod{561}.$

Prove that for any positive integer $a$, $a^{561} \equiv a \pmod{561}$. (Hence, $561$ is a pseudoprime with respect to any base. Such a number is called a Carmichael number.) This obviously works for $...
1
vote
1answer
19 views

On an equation that involves the number-of-divisors function and the formula for a sequence of figurate numbers

In this post we try to relate a sequence from The On-Line Encyclopedia of Integer Sequences and a sequence that solves an equation that involves the number-of-divisors function $\sigma_0(n)=\sum_{1\...
1
vote
2answers
138 views

Suppose each of the numbers $a_1,\dots,a_n$ is either $1$ or $-1$ and $S=a_1a_2a_3a_4+a_2a_3a_4a_5+\dots+a_na_1a_2a_3=0$. Prove that $4|n$ [closed]

Here is the problem Suppose each of the numbers $a_1,\dots,a_n$ is either $1$ or $-1$ and $S=a_1a_2a_3a_4+a_2a_3a_4a_5+\dots+a_na_1a_2a_3=0$. Prove that $4|n$ Could someone help me with this problem?...
1
vote
1answer
27 views

Question on binomial expansion - divisibility by power of divisor

By the Binomial theorem, one has that $$(a+b)^n = a^n + \binom{n}{1} \ a^{n-1}b + \binom{n}{2}\ a^{n-2}b^2 + \dots + b^n$$ Let us suppose that $d\mid (a+b)$, where $\mid$ means "divides", ...
1
vote
5answers
85 views

Prove by mathematical induction, that $81\times 3^{2n} - 2^{2n}$ is divisible by $5$ where $n \in \mathbb{Z}^+$

For all $k$, the equation I came up with is $3^{4+2k} = 5m + 2^{2k}$ where $m$ is a positive integer. For all $k+1$, the expression is $3^{6+2k} - 2^{2k+2}$. I tried to plug in the first equation to ...
4
votes
2answers
87 views

Is this an acceptable proof for If $d^{2}\mid a^{2}$ , then $d\mid a$?

Proof. We will prove the contrapositive. Suppose $d\nmid a$. By the division algorithm, $a = qd + r$ for some $q\geq 0 $ and $0<r<\lvert d \rvert$. Then, $a^{2} = (qd + r)^{2} = q^{2}d^{2} + ...
2
votes
2answers
52 views

When we are finding a root to a polynomial say f(x), we put some constant

When we are finding a root to a polynomial say $f(x)$, we put some constant $a=x$ and check whether it is zero or not.Suppose we have successfully found a constant say $a$, then we say that $x-a=0$ is ...
1
vote
2answers
78 views

Are there infinitely many primes which are the sum of the two sides of a right triangle?

Of the first $9.4 \times 10^9$ primitive Pythagorean triplets (generated using $s^2 - r^2, 2rs, s^2 + s^2$), nearly $16.5\%$ are such that the sum of the two orthogonal sides is a primes i.e. $s^2 - r^...
3
votes
1answer
43 views

Pythagorean triplets which satisfy the prime counting function $\omega(n)$

Let $\omega(n)$ be the number of prime factor of $n$. Out of the first $9.2 \times 10^9$ Pythagorean triplets $a^2 + b^2 = c^2$ (in ascending order of the hypotenuse) I found about $1.03 \times 10^7$ ...
0
votes
1answer
149 views

About the characterization of solutions of an equation that involves particular values of the Dedekind psi function

In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. This is an important arithmetic fuction in several subjects of mathematics. As reference I add the Wikipedia ...
2
votes
2answers
84 views

Is the equation $x = \phi(n), x=2k, n,k \in \mathbb{Z}$, where $\phi(n)$ is the Euler totient function, solvable for all evens?

I was just getting my hands dirty solving some equations of the form $x=\phi(n)$ where $\phi(n)$ is Euler totient function. I know that $\phi(n)$ is even for $n\geq 3$. However, I am wondering that: ...
2
votes
0answers
31 views

If $\gcd(a,p)=1$, $p$ is prime, prove that there are $1\le x, y\le [\sqrt p]$ that $ax≡y\pmod p$ or $ax≡-y\pmod p$

If $\gcd(a,p)=1$, $p$ is prime, prove that there are $1\le x, y\le [\sqrt p]$ that $ax≡y\pmod p$ or $ax≡-y\pmod p$ I met this when looking proof of theory which says if $p=4k+1$ then there are $a,b$ ...
1
vote
2answers
78 views

Proving that if $xo + yp = 1$, then $\gcd(o,p) = 1\;$?

I'm currently trying to prove the equation that you see above. I know that it must have something to do with the laws of divisibility, and these rules in conjunction with rules about integers, but ...
0
votes
0answers
25 views

prove that for all $n≥2$ $n^4+4^n$ is not prime [duplicate]

Prove that $4^n+n^4$ is not prime for $n≥2$. I've found if $n≠5k$ then $5$ divides all equation. We get it from residues when divided by $5$. Also it’s clear that if $n=2k$ then equation is not prime ...
0
votes
6answers
99 views

Use induction to prove 8 divides $7^n+3^n−2$ for all positive integers n. [duplicate]

I can't seem to simplify the problem down to $8m$, which makes it divisible by 8. Can anyone help me out and tell where I made a mistake, or if there's another way to solve this. Thanks, new user here ...
4
votes
5answers
104 views

Divisibility induction proof: $8\mid 7^n+3^n-2$

I'm stuck on the following proof by induction: $$8\mid3^n +7^n -2$$ And this is how far I've gotten: $$\begin{aligned}3&\cdot3^n+7\cdot7^n-2\\3&(3^n+7^n-2)+7^n(7-3)-2\end{aligned}$$ Any help ...
2
votes
1answer
50 views

Using quadratic residues and/or reciprocity to prove relative primality?

I have odd positive integers $q$ and $y$, with $3q^2 < y^2 < 4q^2$, such that the following are true: \begin{align} (q^2+9) &\mid (y^2+5)(y^2+29) \\[0.25em] (q^2+2) &\mid (y^2+1)(y^...
1
vote
5answers
53 views

For how many natural numbers(<=100) is $1111^n +2222^n+3333^n+4444^n$ divisible by 10?

For how many natural numbers (0 not included) $n \leq 100$ is $1111^n +2222^n+3333^n+4444^n$ divisible by 10? I factored out $1111^n$ and got $1111^n(1+2^n+3^n+4^n)$. So $1+2^n+3^n+4^n$ must be ...
0
votes
1answer
43 views

How to simplify a fraction that has matrix

Recently, I was studying about optimum beamforming in array signal processing. In it, the maximum output SINR is $$SINR=\frac{W^{H}R_sW}{W^{H}R_{i+n}W}$$ $$and\quad W=R_{i+n}^{-1}a \quad R_s=\alpha^...
1
vote
2answers
62 views

Divisibility Number Theory problem, explanation needed

I can't understand the solution of the following problem: $x$,$y$,$z$ are pairwise distinct natural numbers show that $(x-y)^5$ + $(y-z)^5$ + $(z-x)^5$ is divisible by $5(x-y)(y-z)(z-x)$. No need to ...
-3
votes
2answers
44 views

Answers to these problems in elementary number theory [duplicate]

Let $d,n \in \mathbb{N}$. Show that if $𝑑\mid 𝑛$ then $2^𝑑 − 1 \mid 2^n-1$ Hence show that $2^{25} − 1$ is divisible by $31$ and $127$.
0
votes
3answers
122 views

Triangular numbers divisible by $3$

I can't understand any of sentences from the images below. Since I don't understand almost every possible lines, I'm very troubled for what I should even ask. But I'll try to. Firstly, how is it ...
3
votes
0answers
44 views

On the equation $\psi(-1+2(\psi(n)-n))=n$ involving the Dedekind psi function, as a characterization of Mersenne primes

In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. This is an important arithmetic fuction in several subjects of mathematics. As reference I add the Wikipedia ...
1
vote
2answers
61 views

Proving that $k|(n^k-n)$ for prime $k$

Prove that for any integer $n$,we have $(n^k)- n$ is divisible by $k$ for $k=3,5,7,11,13$ I tried using prime factorization but that does not work here
0
votes
1answer
44 views

Question about divisibility rule by 7 explanation

So I just remembered a question I had a while ago about an explanation of the divisibility by 7 trick where you double the last digit and subtract it from the rest of the number. I think the ...
4
votes
6answers
2k views

Showing that a $3^n$ digit number whose digits are all equal is divisible by $3^n$

Let $c$ be a $3^n$ digit number whose digits are all equal. Show that $3^n$ divides $c$. I have no idea how to solve these types of problems. Can anybody help me please?
0
votes
2answers
43 views

Can I get a percent of number without using decimals?

I am programming in a language that does not support decimal numbers. The language only supports positive or negative whole numbers. Is there a way to calculate the percent of a number only using ...

1
2 3 4 5
100