Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [divisibility]

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

If $a$ and $b$ are integers, $a$ divides $b$ if $b=ca$ for some integer $c$. This is denoted $a\mid b$. It is usually studied in introductory courses in number theory, so add if appropriate.

A common notation used for the phrase "$a$ divides $b$" is $a|b$. It is also common to negate the notation by adding a slash like this: "$c$ does not divide $d$" written as $c\nmid d$. Note that the order is important: for example, $2|4$ but "$4\nmid 2$".

This notion can be generalized to any ring. The definition is the same: For two elements $a$ and $b$ of a commutative ring $R$, $a$ divides $b$ if $ac=b$ for some $c$ in $R$.

Divisibility in commutative rings corresponds exactly to containment the poset of principal ideals. That is, $a$ divides $b$ if and only if $aR\subseteq bR$. For commutative rings like principal ideal rings, this means that divisibility mirrors exactly the poset of all ideals of the ring.

The topics appropriate for this tag include, for example:

  • Questions about the relation $\mid$.
  • Questions about the GCD and LCM.

There are divisibility rule that is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits.

6170 questions
2
votes
4 answers

How do I prove that $6\mid 7^n - 1$ and/or $8\mid \big(\frac{7^n - 1}{6} + \frac{7^{n + 1} - 1}{6} - 1\big)?$

Prove that: $$\forall n \in \mathbb{N}, \ 6\mid 7^n - 1$$ My Attempt: I first let $n = 1$. $$6\mid 7^1 - 1$$ $$\implies 6\mid 6 \ \ \ \color{green}{\checkmark}$$ Now I let $n = 2$. $$6\mid 7^2 - 1$$ $$\implies 6\mid 48 \ \ \…
Mr Pie
  • 9,459
2
votes
5 answers

$2n+1$ and $n^2+1$ are always coprime or their gcd is $5$

Using a spreadsheet, it can be inferred that when $n≡2[5]$, then $\gcd(n^2+1,2n+1)=5$, else $\gcd(n^2+1,2n+1)=1$. Indeed, when $n≡2[5]$, $n^2+1$ and $2n+1$ can easily be shown to be multiples of $5$, so their gcd is at least $5$. But then, I can't…
Jean-Denis Muys
  • 349
2
votes
2 answers

How to find all the positive integers n of 4 digits such that all its digits are perfect squares and n is a multiple of 2, 3, 5 and 7?

I was trying to use the divisibility rules of 2,3,5 and 7 but I becomes very tedious and couldn's solve the problem. I think there could be a faster way to solve it or to apply those rules. Please help me and thank you very much.
Twnk
  • 2,436
2
votes
4 answers

If $p$ divides $a+b$ is it true that $p$ divides $a$ and $b$?

My hunch is that this is true. Consider the prime decomposition of $a$ and $b$, then $p$ cannot divide $a+b$ if it does not appear in the decomposition of $a$ and $b$, so it must divide both numbers. Is my sketch correct?
Dyan Santiago Delos Reyes
  • 23
2
votes
4 answers

Prove that number made only of $91$ ones is composite

How to prove that number $11...1$ (there are exactly $91$ ones) is composite? I considered this number modulo some small primes, but none of them worked.
user128409235
  • 643
2
votes
4 answers

Need help proving that $3\mid(14^{2n} - 1)$ for all n = 0, 1, 2, 3, ...

I've been stuck on this mathematical proof for quite some time now. So far I have tried using the division algorithm to prove the theorem by letting $n = 3 \times q + r\ |\ q \epsilon N$ This gives me three different cases for values of n. (i) $n =…
limeman
  • 23
2
votes
3 answers

Find the largest 4 digit positive integer n such that 10 divides $n^{19}+99^n$

I've solved this problem and got the answer of $9991$. I manually proved how some digits could or couldn't be the ones digit of $n$, but I feel there is a faster way
Gerard L.
  • 2,536
2
votes
2 answers

how many of the resulting number are divisible by 11 but not by 5?

To me, this is a hard problem. Can anyone help me with this? The number 3456 is divisible by 11 and by 5. Give that you change the position of two or more of these four digits, how many of the resulting number are divisible by 11 but not by 5?
learning
  • 1,749
2
votes
2 answers

Prove that if $(a+b)$ divides $a^2$ then $(a+b)$ divides $b^2$

I'm trying to solve the following exercise: "Prove that if $(a+b)$ divides $a^2$ then $(a+b)$ divides $b^2$". It's quite obvious how to prove divisibility for a product, but how to do it for a sum?
user4510038
  • 117
  • 5
2
votes
1 answer

Dividing by something Undefined

I was thinking about trigonometry ratios, in particularly $\cot(\theta)$, which can be defined as $\cot(\theta) = \frac {1}{\tan(\theta)} = \frac {cos(\theta)}{sin(\theta)}$. Though $\tan(90)$ is not defined as you end up getting $\frac{1}{0}$.…
frog1944
  • 2,357
2
votes
1 answer

Prove that n is a multiple of four....

Let $a_1, a_2, a_3,....a_n$be $n$ numbers such that $a_i$ is either $+1$ or $-1$. If $a_1a_2a_3a_4 + a_2a_3a_4a_5 +...+a_na_1a_2a_3=0$, then prove that $4$ divides $n$. Well $2$ definitely divides $n$ because for every $+1$ there should be a…
Coherent Sheaf
  • 1,333
2
votes
1 answer

Finding remainder when ${{45}^{17}}^{17}$ is divided by $204$

Find the remainder when ${{45}^{17}}^{17}$ is divided by $204$ This question came in an examination yesterday and I couldn't solve it. The answer that was given in the solutions booklet stated this: ${{45}^{17}}^{17}$=$17k+11$= $3{k}^{'}…
Karan Singh
  • 553
2
votes
1 answer

Simple equation - prove division

this should be simple. I am helping my son with one assignment but I simply cannot solve it. I really exhausted ideas. The problem is: prove that $\displaystyle {(m^2 + 5m)(m^2 + 5m + 10) + 24}$ can be divided by 24. Any hint?
user120250
  • 377
2
votes
3 answers

Division by $2p+1$

Can $\left\lfloor{\dfrac{x}{2p+1}} \right\rfloor$ be expressed in terms of $\left\lfloor{\dfrac{x}{p}} \right\rfloor$ for prime $p$? How to divide by $2p+1$ by only using division by $p$? EDIT: The above formulation is wrong. I meant "expressed in…
asmith
  • 23
2
votes
4 answers

Division of $q^n-1$ by $q^m-1$, in Wedderburn's theorem

I need this for a proof of Wedderburn's theorem: $$q^m - 1 | q^n - 1 \quad \Rightarrow \quad m|n$$ with $q>1 \in \mathbf{N}$ and $m,n \in \mathbf{N}$. I'd also like to know if it works the other way around: $$m|n \quad \Rightarrow \quad q^m - 1 |…
Romeo
  • 21
1 2 3
…
30 31