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
1
vote
1 answer

How can I show that the following number is not divisible by $p$ prime?

Let $p$ be a prime number. Let $k$ be some natural number and $r$ be some nonnegative integer. Then, I want to show that for $1\leq i\leq p^k-1$, \begin{equation*} \frac{p^{k+r}m-i}{p^k-i} \end{equation*} is not divisible by $p$, where $m$ is not…
User
  • 607
  • 5
  • 12
1
vote
4 answers

$\gcd(p, (p-1)!) = 1$?

Let $p$ be a prime number. Prove that $\gcd(p, (p-1)!) = 1$. I've attempted using the definition of $\gcd$ to solve this, but I haven't reached a conclusion. Any ideas?
E 4 6
  • 243
1
vote
1 answer

$a^n\mid b^n$ if and only if $a\mid b$.

Suppose $a$, $b$, $n$ are positive. Prove that $a^n\mid b^n$ if and only if $a\mid b$. I know that this can be proved through prime factorization, but I want to prove it using other methods. I understand that the if and only if statement requires…
E 4 6
  • 243
1
vote
0 answers

Find the Conditions

Let $a, b, c, d, r, s \in \mathbb{N}$. Find the necessary and sufficient conditions under which $r \mid (a-b)$ and $s \mid (c-d)$ $\implies$ $\operatorname{lcm}$ $(r,s)\mid(ac-bd)$. A little thought is enough to find out some necessary…
William Hilbert
  • 1,223
1
vote
2 answers

If $b\mid x-y$, $b\in \mathbb{N}$, $b\geq 2$, in this inequation,$-(b-1)\leq x-y\leq b-1$, why the only integer divisible by $b$ is zero?

I didn't understand how they reached at this conclusion: If $b\mid x-y$, $b\in \mathbb{N}$, $b\geq 2$ In this inequation: $$-(b-1)\leq x-y\leq b-1$$ The only integer divisible by $b$ is zero. (Why only zero??) Then $x=y$
Voyager
  • 1,042
1
vote
2 answers

Prove: $\text{if }a,b,c\in\mathbb{Z} \text{ and } a^2+b^2=c^2\text{ then }3\mid ab$

This is for a homework assignment. I am supposed to prove, $$\text{if }a,b,c\in\mathbb{Z} \text{ and } a^2+b^2=c^2\text{ then }3\mid ab$$ I've tried using direct proofs and proofs by contrapositive, but I can't seem to get anywhere. Is there a good…
honey.mustard
  • 331
1
vote
2 answers

Find the sum of all three-digit natural numbers that are not exactly divisible by 3.

Find the sum of all three-digit natural numbers that are not exactly divisible by 3, is the question. What quick ways are there of doing questions like these? Say it was, sum of all three digit natural numbers that are multiples of 14, but not 21?
Jim
  • 1,210
1
vote
1 answer

gcd and linear combinations proof

I'm trying to do extra book work to prepare for our final coming up but a lot of the book questions involve topics I'm unsure about. Prove: $n\in Z$, n=a multiple of gcd(a,b) $\iff$ n is a linear combination of a and b This question makes no sense…
Mikky Davey
  • 225
1
vote
3 answers

How to get a number that is divisible by $n$ - without obviously seeing it?

There are lots of tricks where someone has to think of a number and you can 'guess' that number by just asking a couple of questions (see, for example, here). I'm looking for something kind of similar: a way to change an unknown number (by…
vauge
  • 323
1
vote
2 answers

For any integer $a$, $\gcd(11a+5,2a+1)=1$.

How would I go by proving this statement? What I did was I tried using Proposition GCD Of One, so that $(11a+5)x + (2a+1)y = 1$, and $(11x+2y)a + (5x+y) = 1$. But I have no idea what to do from here. What can I do?
Haxify
  • 435
  • 1
  • 3
  • 8
1
vote
5 answers

Let $n\ge 2$ be an integer. If $\gcd(a,b^n)=1$, then $\gcd(a,b)=1$

Then I know $ax+b^ny=1$, but I can't figure out what to do from here. What could I do to prove this?
Haxify
  • 435
  • 1
  • 3
  • 8
1
vote
1 answer

When does $m$ divide $a^m$?

Let $a\ge 0$, $m\ge 1$ be integers. What can be said about $m|a^m$? I note that if $a=1$, then $m\not{|} a^m$ unless $m=1$ and if $a=0$, then always $m|a^m$. Are there any general results for the less trivial cases? In particular, for any $a\ge 0$…
mathse
  • 2,438
  • 12
  • 18
1
vote
1 answer

Please help to prove the following.

a,b and c are integers and we know that a+b+c=(a-b)(b-c)(c-a) Prove, that a+b+c is divisible by 27. Thank you very much.
user139848
  • 11
1
vote
3 answers

Looking for the lowest number divisible by 1 to A.

What would the math equation be for finding the lowest number divisible by 1 to A? I know factorial can make numbers divisible by 1 to A but that dosn't give me the lowest number. Example of what I'm talking about: the lowest number divisible by…
Binary Freak
  • 107
1
vote
5 answers

Find a polynomial $h(x)$ of maximum degree such that $h(x)$ is a factor of $f(x)$ and $g(x)$

Let $f(x)= x^3-x$ and $g(x)= x^4 + 3x^3 +x^2$ How can I find a polynomial $h(x)$ of maximum degree such that $h(x)$ is a factor of $f(x)$ and $g(x)$. My thoughts: there exist others polynomials $t_1(x)$ and $t_2(x)$ such that $g(x) = h(x)t_2(x)$…
anto.1501
  • 93
1 2 3
…
30 31