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
2
votes
0answers
54 views

On the diophantine equation $x^{m-1}(x+1)=y^{n-1}(y+1)$ with $x>y$, over integers greater or equal than two

I don't know if the following diophantine equation (problem) is in the literature. We consider the diophantine equation $$x^{m-1}(x+1)=y^{n-1}(y+1)\tag{1}$$ over integers $x\geq 2$ and $y\geq 2$ with $...
1
vote
0answers
28 views

Determining which members of a set are an integeral multiple of a member of a different set

I'm given two sets with a regular formula for the terms of each set. $A=\left\{3,7,15,31,\cdots,2^{(n+1)}-1,\cdots,2047\right\}$ $B=\left\{3,5,9,17,\cdots,2^n+1,\cdots,2^{22}+1\right\}$ The question ...
5
votes
1answer
80 views

Mordell equation with prime-squared constant

I'm interested in a specific case of the Mordell equation: $$E: y^2=x^3+k$$ where $k=p^2$ for some prime $p$. Most of the literature I've been able to find regarding the Mordell equation either ...
-1
votes
2answers
72 views

If $ a-b \mid ax-by$, then $\gcd(x,y) \ne1$? [closed]

So is this true for positive integers $a,b,x,y>1$ with $a>b$ and $x>y$?
1
vote
0answers
39 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 ...
19
votes
0answers
300 views
+500

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$ ...
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$ ...
0
votes
3answers
39 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 ...
0
votes
2answers
60 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 ...
1
vote
2answers
71 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 ...
1
vote
3answers
139 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.
4
votes
0answers
62 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
30 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
41 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?
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, ...
6
votes
1answer
90 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{...
1
vote
1answer
20 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
1answer
29 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
87 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 ...
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 ...
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} + ...
1
vote
2answers
80 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$ ...
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 ...
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$ ...
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 ...
1
vote
5answers
54 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
63 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
45 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$.
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^...
3
votes
0answers
45 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
3answers
123 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 ...
0
votes
0answers
20 views

$T$-Annihilators divided by gcd divide another $T$-Annihilator

I have a problem proving the following statement: "Let $V$ be a $K$ Vector-space with finite dimension, let $T \in \text{End}_K(V)$, define $p,q,h \in K[X]$ ($K[X]$ is the polynomial ring with ...
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 ...
5
votes
0answers
50 views

How to decide whether $n+\varphi(n)$ can divide $n^2+k$?

How can we decide whether for a given positive integer $k$ , $\varphi(n)+n$ can divide $n^2+k$ , where $\varphi(n)$ denotes the totient function ? Some cases are easy : $n=1$ is a solution for odd $k$...
0
votes
1answer
53 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 ...
-1
votes
3answers
50 views

$2^r-1$ divides $2^{rs}-1$ [duplicate]

For a composite number $n, n=rs,$ where $n>s≥r≥1.$ Show that $2^r-1$ divides $2^n-1$. Thank you.
0
votes
0answers
13 views

Divisibility criterion in reduced combination formula

From a set of $n$ items, $k$ ($n > 0$ and $0 \leq k \leq n$) items can be chosen in $n \choose k$ ways where the order doesn't matter. Now, $$ {n \choose k} = \dfrac{n!}{k!(n-k)!} = \dfrac{n(n-1)\...
1
vote
1answer
26 views

If a divides $b-1$ and a divides $c-1$ then a divides $bc-1$

I am wondering if the proof I did for this problem is correct. We know a divides b-1 so $b-1=a(t)$ for some integer t also a divides c-1 so $c-1=a(r)$ for some integer r, so by this logic so then $b=a(...
3
votes
1answer
59 views

Find all $a\in\mathbb{N}$ such that $3a+6$ divides $a^2+11$

Find all $a\in\mathbb{N}$ such that $3a+6$ divides $a^2+11$ This problem has stumped me. I don't even know where to begin solving it. I know the solutions will be all $a$ such that $$\frac{a^2+11}{3a+...
0
votes
3answers
61 views

Prove that 9 divides $7\cdot5^{2n}+2^{4n+1}$ [closed]

We have to prove that the following statement is true for all non zero natural numbers: $$9|7\cdot5^{2n}+2^{4n+1}$$
0
votes
0answers
19 views

Multivariate division by a simple factor

Let $f$ be a polynomial in $\mathbb{C}[x_1,...,x_n]$ such that $x_i = x_j$ implies that $f = 0$. This means that there exists a polynomial $g$ such that $f = (x_i - x_j)g$. Is there a "simple&...
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 $...
2
votes
2answers
53 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
votes
1answer
56 views

Looking for divisibility by 29 and a general proof( if any) [closed]

Is there any elegant way to prove that 28C14 -1 is divisible by 29? Also, is this kind of a result a theorem or a generalisation? If so please do help... note i do mean 28 choose 14
0
votes
0answers
27 views

Let a and b be two positive integers with $d = \gcd(a,b)$. Show that $\gcd\left(2^a-1,2^b-1\right) = 2^d-1$. [duplicate]

Let a and b be two positive integers with $d = \gcd(a,b)$. Show that $\gcd\left(2^a-1,2^b-1\right) = 2^d-1$.
0
votes
2answers
32 views

a and b both divide c and are coprime; does ab then also divide c?

I believe that I intuitively understand that if $a$ divides $c$ and $b$ divides $c$ and if $a$ and $b$ are coprime, then their product $ab$ must also divide $c$. What would be a convincing proof of ...

1
2 3 4 5
100