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

learn more… | top users | synonyms

2
votes
5answers
87 views

Inductive proof that $n(n-1)(n+1)$ is divisible by $6$

I am trying to prove that $n(n-1)(n+1)$ is divisible by $6$ for all $n$ in $\mathbb{N}$. My attempt: The result certainly holds for $n=0$. Suppose now that $n > 0$. Assume that $P(k)$ is true for ...
-1
votes
4answers
1k views

Divide by a number without dividing.

Can anyone come up with a way to divide any given x by any given y without actually dividing? For example to add any given x to any given y without adding you would just do: $x-(-y)$ And to ...
0
votes
1answer
301 views

Finding Pitch Diameter of sprocket

I am currently following a tutorial on Instructables here. In the instructable to find the pitch diameter of a sprocket they use the formula on the above link. the pitch that is used is 12.70, the ...
1
vote
2answers
1k views

Proof: Subsequence of n integers is divisible by n?

So I'm confused and stuck on how to approach this question. Any direction in the right path would be greatly appreciated. Let $n\in N$. Prove that any sequence of $n$ integers $a_1, a_2, ... a_n$ (no ...
1
vote
0answers
70 views

The elegant expression in terms of gcd and lcm - algebra - (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to \frac{P+k}{...
3
votes
1answer
2k views

Prove that any integer divides zero: $a\in \mathbb Z \implies a\mid0$

Prove that any integer divides zero: $a\in \mathbb Z \implies a\mid0$ How can i prove that any integer divides zero? i tried using the definition of divisibility, but i dont know if for the formal ...
0
votes
1answer
62 views

If dividing $n$ by $m$ yields remainder $r$, then dividing $-n$ by $m$ yields remainder $-r$

Let m and n be positive integers and let r be the nonzero remainder when n is divided by m. Prove that when -n is divided by m, the remainder is m - r So far I've tried I get n = qm + r and -n = q'm ...
6
votes
0answers
65 views

Divisibility sequence resulting in limit with pi

Consider the following sequence of operations : Start with a natural number $n$ and then round it up to the closest multiple of $n-1$ .Then round up this new number to the closest multiple of $n-...
-1
votes
1answer
83 views

Prove or disprove f an integer is divisible by 4, then it is divisible by 8

I need to know if I can prove or disprove if an integer is divisible by 4 then it is divisible by 8,for this question should i just show a value like 12 to show this statement is wrong or what? How ...
3
votes
1answer
266 views

Prove that if 2 divides $x^2-5$ then 4 divides $x^2-5$

so I have to prove this and I use two different types of proof and I came to a contradicting result. Can someone point out an error I made? Using a direct proof: If 2 divides $x^2-5$ than $x^2-5=2k$ ...
-2
votes
2answers
187 views

Divisibility of subsets of the set $1, 2, 3, …, n$ [closed]

Let $n$ be an even positive integer. Can one divide the numbers $1, ..., n$ into three nonempty groups, so that the sum of numbers in the first group is divisible by $n + 1$, in the second one by $n + ...
0
votes
2answers
39 views

4 Divides x Proofs of conjectures

Hi there I'm working on a set of problems and I'm having some difficulty proving and disproving these examples. I know that #1 is essentially (There exists K where [x=4k]) I'm lost after that. I'm not ...
1
vote
4answers
1k views

If n is a positive integer and 2 divides $n^2$ then 4 divides $n^2$

Best way is to prove by induction? So base case, $n=2$ then $2^2 =4$ which $2$ and $4$ divides $4$ Induction Suppose $2$ divides $n^2$ then $2$ divides $(n+1)^2$?
3
votes
2answers
79 views

Is there a mathematical definition for the “divisibility” of rational numbers?

The term divisibility usually refers to integer numbers only. I want to define the divisibility of a rational number $q$ by an integer number $z$ as follows: $q$ is divisible by $z$ if and only if $...
1
vote
1answer
35 views

Simple Division Problem

I have the equation: $$(1-\frac{1}{2^2})...(1-\frac{1}{n^2}) = \frac{n+1}{2n}$$ for n ≥ 2 Trying to prove by induction and I get the following equation. $$\frac{k+1}{2k} + \frac{k(k+2)}{(k+1)^2} = \...
1
vote
1answer
33 views

Greatest common divisor of linear combination of two comprime numbers

How to calculate $\gcd(2n+3m,n-m)$ if $\gcd(n,m)=1$ $\gcd(2n+3m,n-m)= \gcd(2n+3m+ 3(n-m),n-m)=\gcd(5n,n-m)= $ and i don't know. Plase help me
1
vote
1answer
31 views

Prove that 1 less than the number of equivalence classes divides $p-1$ where $p$ is prime

I am faced with the following problem: Let $p$ be a prime number and $\gcd(p,n)=1$. Define an equivalence relation on $\mathbb{Z}_{p}$ as follows: $x \sim y$ iff $n^{r}x = n^{t}y$ for some $r,t ...
-2
votes
1answer
31 views

Divisibility criterion for 11

What is a quick way to prove using induction the following fact: "A number is a multiple of 11 if and only if the sum of its even-placed digits minus the sum of its odd-placed digits is also a ...
5
votes
3answers
172 views

$z=100^2-x^2$. Then, how many values of $x,z$ are divisible by $6$?

$z=100^2-x^2$. Then, how many values of $x,z$ are divisible by $6$? My approach: For $x=1$, $z$ is not divisible by $6$. For $x=2$, $z$ is divisible by $6$. For $x=3$, $z$ is not divisible by $6$...
2
votes
1answer
46 views

Can integers be divisible by real numbers?

I have searched for many definitions of divisibility and they all seem to go like this: Let $a, b \in \mathbb{Z}$ then $b$ is divisible by $a$ if there exists $c \in \mathbb{Z} : b = ac$. Is ...
1
vote
2answers
72 views

4 variables how many combos of 3 can you make

If you have 4 variables A, B, C, D How many combos can you make that use 3 of the variable and are unique (order matters), so I mean A,B,C and B,A,C only counts ...
1
vote
3answers
58 views

For which $n ≥ 0$ is $2^n + 2 · 3^n$ divisible by $8$?

Stuck on this problem for some time: For which $n ≥ 0$ is $2^n + 2 · 3^n$ divisible by $8$? I've reached the conclusion that $n = 1$ is the only solution to the question at hand, but I cant quite ...
15
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
1
vote
2answers
55 views

Finding how many numbers are divisible by a prime number

I'm trying to figure out how I can find out how many numbers are divisible by a certain prime (eg 3) in a certain range, eg 0-10000. I think it has something to do with permutations, but I'm not ...
0
votes
3answers
54 views

Why are every number (integer) exactly divisible by 5 in decimal number system but not in binary number system?

I have wondered during the number system classes in computer science that if 1/5 in decimal number system results in 0.2 why <...
1
vote
5answers
99 views

Mathematical Induction Divisibility Problem

Prove that if $n \ge 1$ is a positive integer, then $13^n − 6^n$ is divisible by $7$. In proving the $n = k+1$ case, I get to $133k + 6^k\cdot13 - 6\cdot13^k = 7M$, where $M$ is a positive integer. $...
3
votes
2answers
52 views

Number of ordered pairs $(x, y)$ such that $0 \leq x, y\leq 18$ and $3x+4y+5$ is divisible by $19$

The problem would have been much simpler if there was no constant term, (like $3x+4y$ divisible by 19) because then all the solutions could have been generated from just the solution to $3x+4y=19$. ...
0
votes
2answers
44 views

A simple question about divisibility: If $n$ divides the product of coprime numbers…

This is quite basic, but I'm no good at this stuff, and I've basically just been sitting her trying to find counterexamples... If $n$ divides $jk$, where $gcd(j,k)=1$, must $n$ divide $j$ and $k$? Or,...
0
votes
2answers
44 views

How to prove that $4n^2+4n+8$ is even?

I'm trying to prove that $4n^2+4n+8$ is even. I tried dividing the polynomial by $2n$ to get a remainder of $8$. Is this correct? how do I proceed ?
2
votes
1answer
25 views

Prove $ax=ay \pmod {p^2}$ implies $x=y \pmod {p^2}$

Let $p$ be a prime and $a$ an integer not divisible by $p$. Prove $ax=ay \pmod {p^2}$ implies $x=y \pmod {p^2}$ $p^2$ divides $a(x-y)$ implies $p$ divides $a(x-y)$. $p$ does not divide $a$ implies $p$...
1
vote
1answer
25 views

Greatest common divisor of 2n+1 and 9n+4

Calculate $GCD(2n+1,9n+4)$ and $GCD(2n-1,9n+4)$ $$GCD(2n+1,9n+4)=GCD(2n+1,9n+4-4 \cdot (2n+1))=GCD(2n+1,n)= GCD(n,1)=1$$ How to calculate $GCD(2n-1,9n+4)$
0
votes
7answers
133 views

Prove by induction that $73\mid 8^{(n+2)}+9^{(2n+1)}$

The problem asks to prove $8^{(n+2)}+9^{(2n+1)}$ is divisible by 73 Proof by induction: We look at base case $n=1$ => which gives us $1241$ which is divisible by $73$; now for $n+k$ we know that $8^...
0
votes
1answer
26 views

Finding number of integers divisible by 2, 3 or 4 using inclusion-exclusion principle.

I want to find number of integers from 1 to 19 (both included) which are divisible by 2 or 3 or 4. Lets denote it by N. So counting and enumerating them gives N = 12. Integers are 2, 3, 4, 6, 8, 9, 10,...
3
votes
0answers
109 views

Find the fundamental group and the Alexander polynomial

I would like to find the Alexander polynomial of the link $L$, described below. Let $K(q,r)$ be the $(q,r)$-torus knot embedded on a torus $V$. Inside the torus $V$, consider a smaller solid torus $V'...
0
votes
1answer
46 views

Find all non-negative integers $n$ satisfying $2^{n}\equiv n^{2} mod\, 5$

I'm trying to find all non-negative integers $n$ satisfying $2^{n}\equiv n^{2}\pmod{5}$. So far, all the progress I've made is figuring out that $n^{2} mod \, 5$ for $n=1$ to $5$ has the pattern "$...
3
votes
2answers
153 views

Does $\gcd(a,bc)$ divides $\gcd(a, b)\gcd(a, c)$?

I want to prove that $\gcd(a,bc)$ divides $\gcd(a,b)\gcd(a,c)$ but I can't succeed. I tried to go with $\gcd(a,b) = sa+tb$ and it didn't work, tried to use the fact that $\gcd(a,b)$ and $\gcd (a,c)$ ...
0
votes
2answers
56 views

Division theorem for polynomials with integer coefficients

I can see that the Division Theorem holds for polynomials in $\mathbb{Q}[x]$, but does not necessarily hold for polynomials in $\mathbb{Z}[x]$, e.g. Let $f=x^2+3x$ and $g=5x+2$. Then the Division ...
3
votes
2answers
216 views

Relatively prime numbers and divisor

If $a | c$ and $b | c$ and $a$ and $b$ are relatively prime prove that $ab|c$. What I did was since $(a,b)=1$ then we can find integers $m,n$ such that $ma + nb=1$. Now since $a|c$ then $a = mc$. ...
0
votes
1answer
50 views

Better proof of $X^5=Y^2+4$ has no solutions in $\bf Z$?

Consider: $X^5=Y^2+4$ $X,Y \in \bf Z$. If $11 \not | X \rightarrow X^{10}-1\equiv 0 \pmod {11}\rightarrow (X^5-1)(X^5+1)\equiv 0 \pmod {11} $. From here we do a remainder table for all numbers and ...
7
votes
2answers
1k views

Showing that gcd does not exist for $3(1+\sqrt{-5})$ and $3(1-\sqrt{-5})$ in $\mathbb Z[\sqrt{-5}]$.

An exercise asks me to show that $3(1+\sqrt{-5})$ and $3(1-\sqrt{-5})$ have no greatest common divisor in $\mathbb Z[\sqrt{-5}]$. I think I have to find two maximal common divisors which are not ...
0
votes
0answers
31 views

On $\sum_{k\nmid n}k$, where the sum is over the integers $1\leq k\leq n$ such that $k\nmid n$, and perfect numbers

If we define the arithmetic function $\delta(n)$ as the sum of integers $1\leq k\leq n$ such that $k\nmid n$, we have by Gauss statement $\sum_{k=1}^n k=n(n+1)/2$, that $$\sigma(n)+\delta(n)=\frac{n(...
1
vote
1answer
32 views

How do i work out the added 20% from the final result

According to my employee contract because I am casual I am being paid with an extra 20% loading making my total being $22/h. I wanted to work out how much I would normally have been paid if I wasn't ...
1
vote
7answers
954 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg P\...
1
vote
2answers
49 views

Does the LCM of $ax$ and $bx$ equal $\operatorname{lcm}(a,b)\cdot x$?

Let $a,b,x \in Z^+$. Prove that $\operatorname{lcm}(ax,bx) = \operatorname{lcm}(a,b)\cdot x$. Here are my thoughts: Let $d = \operatorname{lcm}(ax, bx)$. By definition $ax|d$ and $bx|d$. Now it can ...
23
votes
6answers
18k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out why ...
2
votes
2answers
69 views

Checking whether a number is prime or composite

This is a question that came up while I was doing an exercise. I ended up with the number $$ 200! + 1$$ and I want it to be composite but I don't know of any methods to check whether a number is ...
0
votes
4answers
79 views

Showing $n^3 - n$ is divisible by $6$ [duplicate]

How would you show that $n^3-n$ is divisible by $6$, when $n=k+1$ ?
3
votes
0answers
53 views

In any set of ten consecutive positive integers, there is one that is coprime with each one of the others [duplicate]

Let $a$ be a postive integer and let $A=\{a,a+1,a+2,\ldots,a+9\}.$ Show that there exists some $i$ such that for any $j\neq i$ we have $(a+i,a+j)=1$
0
votes
2answers
35 views

If a number cannot be…

If there exists such a number which cannot be divided by some other number, which is equivalent to, or smaller than the square root of itself, it is a prime number. This is a rather trivial theorem ...
2
votes
1answer
26 views

If $x$ divides $x-z$, then $x$ divides $z$

For any integer x and z , if $x|(x-z)$ then $x|z$ My attempt: suppose $x|(x-z),$ let $y= x-z$ $x|y $ means there is any integer r such that $y=r*x$ So $ x-z=rx $, which equals $(x-z)/(x) =r $ ...