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
3
votes
1 answer

The percentage of a number to zero

let's imagine that a student got 0 marks in a exam. And in the next one he got 5 marks. to calculate the percentage of the new mark to the last mark, we usually use (new-last)/last*100%. but the denominator is 0. So the expression should be…
Alexander Ho
  • 131
  • 1
  • 5
3
votes
7 answers

Direct Proof on Divisibilty

Using Induction proof makes sense to me and know how to do, but I am having a problem in using a direct proof for practice problem that was given to us. The problem is: For all natural numbers $n$, $2n^3 + 6n^2 + 4n$ is divisible by 4. We are to use…
user3321427
  • 61
3
votes
5 answers

I am looking to show that $n$, $n + 1$, or $n + 2$ are divisible by 3

I am seeking to prove the following: If $n \in \mathbb{Z}$, then exactly one of the following is true: $\frac{n}{3} \in \mathbb{Z}, \frac{n + 1}{3} \in \mathbb{Z}, \frac{n + 2}{3} \in \mathbb{Z}$. I believe this is pretty self evident, and hence…
Will Pike
  • 131
3
votes
4 answers

Solutions of $2^a - 7 = 27b$

How can I find the solutions of the equation $2^a - 7 = 27b : a, b \in \mathbb{N}$? I can see this is also of the form $2^a - 7 \equiv 0 \mod 27$.
Don Larynx
  • 4,703
2
votes
3 answers

Prove if $a|c$ and $b|d$ and $\gcd(c,d)=1$ then $\gcd(a,b)=1$

I'm trying to prove that if $a|c$ and $b|d$ and $\gcd(c,d)=1$ then $\gcd(a,b)=1$ So far, I have assumed that: Since $\gcd(c,d) = 1$ then by EEA, $$\gcd(c,d) = 1 = cx + dy$$ for some $x,y$ that are integers. And since $a|c$ and $b|d$ then $c=am$ and…
Matmatic
  • 23
2
votes
0 answers

Using divisibility and greatest common divisor for a proof

If u|t and v|t and gcd(u,v)=1, then prove that (uv)|t I started by analyzing the definition of divisibility and I got that (uv)|t^2, but this doesn't help me. Any advice would be appreciated. Thank you :)
Ian Murphy
  • 196
  • 13
2
votes
2 answers

Algorithm to find the coefficient of GCD linear combination?

One of the properties of the GCD of two integers is that it can be written as the linear combination of the two, is there an algorithm that can be used to find the coefficients of this linear combination?
DennisKRQ
  • 435
2
votes
1 answer

N is a number in base 9.Find N when n is divided by 8(in base 10)?

N is a number in base 9.Find N when n is divided by 8(in base 10)? And N can be very large.say N=32323232.....50 digits This can be done by converting N to base 10.But time consuming. What will be the fastest approach given that no proof is…
lliB the Lizard
  • 61
2
votes
1 answer

prove by contradiction that $ax+by=c$ has no integer solutions if $c$ does not divide into $\gcd (a, b)$

Prove by contradiction that (the diophantine equation) $ax+by=c$ has no integer solutions if $c$ does not divide into $\gcd (a, b)$. Here is what I did: lets assume $c$ divides into $\gcd (a, b)$. There are infinitly many solutions if $c$ divides…
bool
  • 21
2
votes
0 answers

Prove the congurence

I am looking for a proof of Gauss's generalization of Wilson's Theorem. Let $S$ be the set of all the integers which are less than and mutually prime to $n (>4)$ (not of the form $p^\alpha$, $2p^\alpha$ for all odd $p$). Denote the elements of $S$…
William Hilbert
  • 1,223
2
votes
1 answer

Properties of Integers

A theorem presented in my discrete math book. Let $d$ be the smallest positive integer of the form $ax + by$. Then $d = \gcd(a,b)$, where gcd means greatest common divisor. I don't understand how the variable $d$ being the smallest possible…
user71181
  • 253
2
votes
1 answer

Find all positive integers n such that $n\mid\lfloor(n-1)!/(n+1)\rfloor$

Find all positive integers $n$ such that $n\ \big|\ \left\lfloor\frac{(n-1)!}{n+1}\right\rfloor$. The answer says that when $n<5$, the condition holds for $n=1$ only. But I think $n=2,3$ also hold. Which is correct?
user138079
  • 33
2
votes
1 answer

Is my proof correct? Let $a, b, c\in\mathbb Z$. Prove that if $a\mid b$ and $b\mid c$, then $a\mid(b + c)$.

Let $a$, $b$, $c$ $\in\mathbb{Z}$. Prove that if $a\mid b$ and $b\mid c$, then $a\mid (b + c)$. My proof: since $a\mid b$, $b = k\cdot a$ for some integer $k$ since $b\mid c, c = l\cdot b$ for some integer $l$ then, $c = l\cdot k\cdot a$, $a\mid…
user143251
  • 65
2
votes
0 answers

$27^{2004} + 22^{2004} - 4^{2004} - 1$ is divisible by (options)

(A) $299$ (B) $296$ (C) $298$ (D) $297$ This kind of sums are too problematic. Please provide a method which could give the correct answer in about a minute. :)
Harshal Gajjar
  • 1,664
2
votes
1 answer

$\forall (p,k)\in\mathbb N^2$ with $k$ not divisible by $3$ : $1+p+p^2\mid 1+p^{2k}+(1+p)^{2k}$

I want to prove $\forall (p,k) \in\mathbb{N}$$^{2}$ with k not divisible by $3$ : $1+p+p^2\mid 1+p^{2k}+(1+p)^{2k}$ An attempt. $1+p+p²=(p-j)(p-\bar{j})$ with $j=e^{i\frac{2\pi}{3}}$. Then I prove that j and $\bar{j}$ are roots of the polynomial…
yoda
  • 315
1 2 3
…
30 31