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

Proof of divisibility

I am looking at a fairly simple problem yet I can't figure it out. Prove that $16x^4+32x^3+32x^2+16x$ is divisible by 96 for every positive integer x. I've tried factoring, but I cannot figure out how to prove this.
ampersander
  • 521
0
votes
2 answers

if $a$ is prime to $b$ and $y$, $b$ is prime to $x$ then prove that $ax+by$ is prime to $ab$

I think this question is incorrect as: let $ax+by = p, then, (a,b)|p, (a,y)|p, (x,b)|p, (x,y)|p$ now : $(a,b) = (a,y) = (x,b) = 1$ now let $p = m(x,y)$ so left to prove $(ax + by, ab) = 1$ which is the same as: $(m(x,y),ab) = 1$ but $m$ might be…
AYUSHROCKS123
  • 83
0
votes
0 answers

Let $a_1,a_2,b_1$ and $b_2$ be elements in an integral domain $D$. Show that $a_1|b_1$ if and only if $a_2\mid b_2$

We may assume that $a_1$ and $a_2$ are associated, and that $b_1$ and $b_2$ are associated. So here is what I've got so far: Lets assume that $a_1|b_1$. By definition, this is: $b_1=a_1\cdot c$ for some $c\in D$. By associativity, $a_1=a_2\cdot u_1$…
Max
  • 123
0
votes
1 answer

If $x^2 y^5 z$ is exactly divisible by 9, what is the least value of $(x+y+z)$?

I did find the solution on Internet here. But I am not able to understand it completely.
Noorul Quamar
  • 115
0
votes
1 answer

If $n \in \{4k\}, k \in \mathbb{N}$ , then $(\frac{n}{2})^2 \equiv 0$ mod $n$.

So I've noticed that if $n \in \{4k\},$ with $k \in \mathbb{N}$ then $(\frac{n}{2})^2 \equiv 0$ mod $n$. Example $2^2 \equiv 0$ mod $4$, $4^2 \equiv 0$ mod $8$, $8^2 \equiv 0$ mod $16$, and so on... I wanna go about proving this but I'm not entirely…
SunRoad
  • 65
  • 5
0
votes
0 answers

The number $2^{3^n}+1$ is divisible by $3^{n+1}$ and is not divisible by $3^{n+2}$.

Old question: The number $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$. However, I don't understand the answer from the question. I know how to prove why it is divisible by $3^{n+1}$, but not divisible by $3^{n+2}$. Prove it…
Business Man
  • 17
  • 5
0
votes
0 answers

$n^2 +1$ is not divisible by 3 for any integer n

So I understand the basic concept of when $n=3k $ $(3k)^2 + 1 = 9k^2 + 1 = 3(3k^2) + 1 $ But I saw a solution when we use $3k+ 1$. for example for $(3k+1)^2 + 1 = 9k^2 + 6k + 1 + 1 = 3(3k^2 + 2k) + 2.$ where does the 6 come from? Same goes for $3k…
Dani
  • 1
  • 3
0
votes
2 answers

How to find if a number has any odd divisor (greater than 1)?

I want to build an algorithm which tells if a number has any odd divisor or not. for example, 6 has an odd divisor 3 (greater than 1), 4 doesn't have any odd divisors, and so on. I know that I can find all the pairs of divisors by only traversing…
Sreshtha Mehrotra
  • 35
0
votes
2 answers

Positive integer solution such that $7^m - 3^m$ is prime

Find all $m \in \mathbb{Z}$, for which the expression $7^m - 3^m$ a prime. What would be the general strategy for solving this? I have no clue where to begin. I tried picking $m$ and checking some values but I don't see any relation between them.…
UnKnoWnZ
  • 167
0
votes
2 answers

Prove that it doesn’t exist $n\geq3$ Such that $n$ is divisible by all $m\le n$

A Claim: Let $A$ be a set contains all $n\geq3$ Such that $n$ is divisible by all the numbers less or equal to $n$. $$A=\{n\geq3 \mid m\mid n, \forall m\le n \}$$ Show that $A=\emptyset$. This is just another way to explain the question in the…
PNT
  • 4,164
0
votes
1 answer

CRT and systems of modular equations

The formula I found: $$\sum_{i=1}^{k} a_{i}b_{i}b^{`}_{i} (\mod m_{i})$$ where: $b_{i} = \frac{M}{m_{i}}$ $b_{i}^{`} = b_{i}^{-1} (mod m_{i})$ And for example: $$x \equiv -7 \mod 13$$ $$x \equiv 39 \mod 15$$ $M = 13*15 = 195$ $b_{1} = 13$ $b_{2} =…
khernik
  • 1,369
0
votes
2 answers

How to find the lowest whole divisor of a number?

How do I find the lowest divisor of a number so that if we divide the number by the divisor we will get a whole number? I need a basic formula. (This is for coding.)
Amit Assaraf
  • 1
0
votes
1 answer

Proving divisibility if and only if also divisible by factors

I need to prove, that $10|a$ if and only if $5|a$ and $2|a$. Divisibility properties say, that if $a|b$ then b is also divisible by $a$-s factors. I think I need to show that $10|a$ and then that it is also divisible by it's factors. Am I going the…
kyng
  • 115
0
votes
1 answer

Divisors of $z$ and $m$ compared to divisors of $z$ and $mn$, where $(m,n) = 1$.

Suppose $(m,n)=1$. Then is it true that the common divisors of $z$ and $m$ are exactly the common divisors of $z$ and $mn$? If not, is it true that the second set is a subset of the first? This is probably a very simple question, but I cannot get my…
JBuck
  • 681
0
votes
2 answers

Sum of reciprocals of powers of 3 equals 3/8?

Let $A=\{ \sum_{i=1}^\infty \frac{x_i}{3^i}: x_i = 0 \,\text{ or }\, 2 \}$, show that $\frac{3}{4} \in A$ My attempt: Let $2\bigl(\frac{1}{3^{n_1}}+\frac{1}{3^{n_2}}+\frac{1}{3^{n_3}} + \dotsm\bigr) = \frac{3}{4}$ $\Rightarrow…
Monalisha Bhowmik
  • 297
1 2 3
…
30 31