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

learn more… | top users | synonyms (1)

1
vote
1answer
38 views

Divisibility problem: $ \frac{3^{m}}{2^{n} - 3^r} $

Is divisible a power of 3 for a difference of powers of 2 and 3? That is, can result, this division, in an integer? $$ \frac{3^{m}}{2^{n} - 3^r} $$ where $n,m,r$ natural number. Edit: $n>r$, ...
0
votes
0answers
40 views

I need help prooving a theorem in OEIS A224914

I've tried to solve this, but can't seem to get anywhere. Full description is in the pdf. http://blogoff.simonjensen.com/#post18 http://www.simonjensen.com/pdf/The_answer_is_47.pdf ...
1
vote
3answers
42 views

Divisibility proof problem

I need assistance with the following proof. Let a,b,c,m be integers, with m $\geq$ 1. Let d = (a,m). Prove that m divides ab-ac if and only if $\frac md $ divides b-c. Alright, I know that since d ...
3
votes
2answers
69 views

Prove by induction $a-b|a^{n}-b^{n}$ for $n\in\mathbb N$

$P(1)$: $a-b|a-b$ $P(n) \Rightarrow P(n+1)$: $a-b|a^{n}-b^{n}\Rightarrow a-b|a^{n+1}-b^{n+1}$ I'm not sure how to proceed from here. Any help is appreciated.
1
vote
3answers
43 views

Prove by induction that $99 | 10^{2n} + 197$ for $n\ge 1$

I'm not sure whether I should make use of the transitive property, or this $a|b\Rightarrow b = a*z$ / $z\in\mathbb Z$ to solve the problem. I'm mainly looking to solve it through induction using the ...
0
votes
2answers
89 views

Writing a GCD of two numbers as a linear combination

I am working on GCD's in my Algebraic Structures class. I was told to find the GCD of 34 and 126. I did so using the Euclidean Algorithm and determined that it was two. I was then asked to write it ...
0
votes
1answer
33 views

Finding the biggest $n$ that is divisible by all $m < \sqrt[3]{n}$

Find the biggest positive integer $n$ such that $n$ is divisible by all positive integers smaller than the integer part of the cubic root of $n$. I'm quite sure it's $420$, but I need proof for ...
2
votes
1answer
71 views

Proving that $n$ doesn't divide $2^n - 1$ for any integer $n > 1$

Prove that $n$ doesn't divide $2^n - 1$ for any integer $n$ bigger than $1$. Thanks in advance! Any questions, please comment!
4
votes
2answers
51 views

For a positive integer $n$ both $5n+1$ and $7n+1$ are perfect squares. Show that $n$ is divisible by 24.

My try: $5n + 1 = k^2$ $7n +1 = \frac{7k^2-2}5$ Just don't know how to proceed after this. Please help.
1
vote
2answers
97 views

How many $7$ digits number can be made?

How many $7$ digits number can be made with $1,2,3,4,5,6,7$ so that they are divisible by $11$? (Repetition is not allowed.) I know the divisibility rule of $11$, so the main problem is counting.
1
vote
6answers
269 views

LCM of First N Natural Numbers

Is there an efficient way to calculate the least common multiple of the first n natural numbers? For example, suppose n = 3. Then the lcm of 1, 2, and 3 is 6. Is there an efficient way to do this for ...
11
votes
1answer
178 views

Family of GCDs all equal to $2$

Is it true that $$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2$$ for all $n \in \mathbf{Z}_{\geq 0}$? I'm continually stumped with this and verifying it numerically is quite expensive very ...
0
votes
1answer
38 views

Subring of Gaussian integers has no greatest common divisor property [duplicate]

Problem is: Produce elements a and b in the domain $R := \{x+2y\sqrt{-1} \mid x, y \in \mathbb{Z}\}$ having no gcd. How can produce this? Actually I use norm function, and brute force, but what ...
3
votes
1answer
94 views

Find two elements that don't have a gcd in a subring of Gaussian integers

Find two elements in the domain $R := \{ x + 2y \sqrt {-1} \mid x,y \in \mathbb{Z} \}$ that do not have a gcd. I have no idea how to start. But I know if we consider $R^\prime = \{ x + y \sqrt ...
0
votes
4answers
77 views

Prove that $2^{2k-1}+2^{k}+1$ is not divisible by $7$ for any $k$ natural number

I am trying to prove this, but I really can't seem to get anywhere with it.. I tried transforming this into something else, but no transformation yields in any useful expression whatsoever.. As ...
0
votes
2answers
116 views

Prove that if $a$ and $bc$ are nonzero integers, then $(ca,cb) = |c|(a,b)$.

Prove that if a and bc are nonzero integers, then $$(ca,cb) = |c|(a,b).$$ Basically, I was confused by the statement of the question. In particular, I was unsure if choosing a and bc to be nonzero ...
0
votes
4answers
113 views

Prove that if a and b are integers, then there are unique integers q and r such that $a = bq + r$, $-|b|/2 < r \le |b|/2$ [closed]

Prove that if a and b are integers, then there are unique integers q and r such that $$a = bq + r,$$ with the restriction that$$-|b|/2 < r \le |b|/2$$
1
vote
2answers
32 views

Euclid algorithm - linear combination

I've been taught that Euclids algorithm for $(a,b), a > b $ can be used to find $x,y$ such that $ax + by = d$, where $d$ is their GCD. However, the only method we have used to obtain this is by ...
4
votes
6answers
195 views

Proof that $a^5 b - b^5 a$ is divisible by $30$ for any integers $a$ and $b$

I am trying to prove that $a^5\times b - b^5\times a$ is divisible by $3$. The actual task is to prove divisibility by $30$ but I have managed to prove that the expression is divisible by $5$ and $2$. ...
0
votes
2answers
26 views

Basic divisibility of large numbers.

So I'm just going through KhanAcademy to refresh my basic pre-arithmetic and although it's embarassing I thought I'd get this thing checked up just for safety: ...
4
votes
1answer
86 views

If $3\mid a,b,c$ and $n=a^2+b^2+c^2$, prove that there exist $x,y,z$ such that $n=x^2+y^2+z^2$, where $3\nmid x,y,z$.

If $3\mid a,b,c$ and $n=a^2+b^2+c^2$, prove that there exist $x,y,z$ such that $n=x^2+y^2+z^2$, where $3\nmid x,y,z$. Here $n\in\mathbb N$, $a,b,c,x,y,z\in\mathbb Z$. This problem is originally ...
0
votes
3answers
65 views

Proving integers are relatively prime

Let $a,b,c$ be nonzero integers. Suppose $a$ divides $(b+c)$ and $(b,c) = 1$. Prove that $(a,b) = 1$. My thoughts: Use the fact that the G.C.D of $a$ and $b$ is the smallest positive integer ...
2
votes
1answer
34 views

If $k$ is composite, which of its prime factors dominates its divisibility into $n!$ for $n$ large?

Suppose we have a fixed (generally composite) $k$, and we want to find the largest power of $k$ that divides $n!$ for $n$ large. If $k$ is square-free, we need only consider the behavior of the ...
2
votes
2answers
42 views

True or false division algorithm problem

Let a,b,c be integers with a not equal to 0 and (b,c)=1. If a divides the product of bc, then a must divide b or a must divide c. My thoughts: I can prove this if (a,b)=1. but I believe it is false ...
1
vote
5answers
125 views

If you have a number that is the difference of 2 squares, is it odd?

I know that the question "Prove that if $n$ is odd, it is the difference between two squares" has been answered here: Prove every odd integer is the difference of two squares But I want to know if ...
10
votes
4answers
241 views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).
0
votes
0answers
30 views

How to find gcd sum for some combination of numbers?

The problem is , Given an n-dimensional hyperrectangle length of each dimension is given. Now the value of each cell is the gcd of its co-ordinates. Now How do we find the sum of all cells ? I have ...
1
vote
2answers
69 views

GCD of the already GCD

Say $a$ and $b$ are integers. $\gcd(a,b)$ is then $d$. Now if $a$ equals $dm$ for some integer $m$ and b equals $dn$ for some integer n, how come the gcd of this m and n is always 1?
5
votes
1answer
65 views

3 incrementing buttons, optimal value

This was asked on PhysicsForums.com and I am very interested in seeing a nice solution. Suppose we want a user to be able to enter any numeric value from 1 to 100. This number is entered by 3 ...
1
vote
1answer
45 views

Find all $n\in\mathbb N$ such that $n\ne k^2$ ($k\in\mathbb N$) and $\lfloor\sqrt{n}\rfloor^3\mid n^2$.

Find all $n\in\mathbb N$ such that $n\ne k^2$ ($k\in\mathbb N$) and $$\lfloor\sqrt{n}\rfloor^3\mid n^2$$ That's a really interesting problem and I can't seem to find an idea for a solution. Some help ...
1
vote
2answers
42 views

Help with a proof envolving a finite group and a specific bijection

Let $G$ be a finite group, and let $k>1$ be an integer. I need to prove that if the mapping $f:G\rightarrow G$, defined by $f(g)=g^k$, is bijection, then $\gcd(k,|G|)=1$. I almost certain that if ...
-1
votes
7answers
59 views

If an integer a is such that a-2 is divisible by 3 then a^2-1 is divisible by 3. prove by direct method

How to prove that if a is number such that $a-2$ is divisible by $3$ then $a^2-1$ is divisible by $3$ using direct method. I know if $a = 2$ then $a-2 = 0$ is divisible by $3$ and $2^2-1 = 3$ is ...
2
votes
0answers
62 views

Find Gcd summation fast?

Find the value of the summation: $$ val=\left( \sum_{i=1}^a \sum_{j=1}^b\sum_{k=1}^c....\sum_{x=1}^p GCD(i,j,k,..x) \right)$$ Contraints $2\leq$number of summation terms$\leq 500$, $1\leq ...
1
vote
1answer
47 views

GCD of $N$ numbers is 1

Given two numbers $m$ and $n$. $\gcd(a_{1},a_{2},\ldots,a_{m})$ is the gcd of number $a_{1},a_{2},\ldots,a_{m}$. How to find number of ways such that $\gcd(a_{1},a_{2},\ldots,a_{m})$ ($1\le a_{i}\le ...
10
votes
1answer
107 views

Find all $x,y,z\in\mathbb N$, $x,y,z>1$ such that satisfy $x\mid yz+1$, $y\mid xz+1$, and $z\mid xy+1$

Find all $x,y,z\in\mathbb N$, $x,y,z>1$ such that satisfy $$\begin{cases}x\mid yz+1\\y\mid xz+1\\z\mid xy+1\end{cases}$$ I've found out easily that $$\begin{cases}x\nmid yz\\y\nmid xz\\z\nmid ...
0
votes
2answers
92 views

Does dividing by zero ever make sense? [duplicate]

Good afternoon, The square root of $-1$, AKA $i$, seemed a crazy number allowing contradictions as $1=-1$ by the usual rules of the real numbers. However, it proved to be useful and ...
1
vote
3answers
40 views

Integers divide several solutions to Greatest Common Divisor equation

I'm not sure about the topic's correctness but my problem is following: Suppose $u_1,v_1$ and $u_2,v_2$ are two different solutions for $au_i + bv_i = 1$, then $a \mid v_2-v_1$ and $b\mid u_1-u_2$. ...
-1
votes
1answer
52 views

Efficient way to find lowest divisor of an integer.

I have followed the given way to find the lowest divisor of an integer, Let us assume n is the given integer. Check n is ...
2
votes
2answers
42 views

Show $\gcd (a,b)=\gcd (b,r)$ if $a = bq + r$

Let $a, b$ be two integers with $b \neq 0$, and $q, r$ non-negative integers such that $a = bq + r$. How can we show that $\gcd (a,b)=\gcd (b,r)$?
2
votes
6answers
101 views

Prove that $4^{2n+1}+3^{n+2} : \forall n\in\mathbb{N}$ is a multiple of $13$

How to prove that $\forall n\in\mathbb{N},\exists k\in\mathbb{Z}:4^{2n+1}+3^{n+2}=13\cdot k$ I've tried to do it by induction. For $n=0$ it's trivial. Now for the general case, I decided to throw ...
0
votes
3answers
28 views

Divisibility of polynomials in $\mathbb{Z}_n[x]$

For what values of $n$ is $x^2+1$ a factor of $x^5+5x+6$ in $\mathbb{Z}_n[x]$? I know how to divide in $\mathbb{Z}[x]$ (with long division), but what should I do here with $\mathbb{Z}_n[x]$, and it's ...
1
vote
2answers
50 views

Divide with remainders in a ring

How is it works ? What is different between divide with remainders in a ring and without ? e.g I have this question: Calculate $\frac{6x^5+2x^4+5x^3+x+2}{5x^3+x^2+6}$ in the ring ...
0
votes
1answer
46 views

How to calculate total number of combination having sum divisible by a given number.

I have following code.And i want to calculate value of ans. ...
0
votes
2answers
41 views

Euclidean lemma proof [duplicate]

According to Euclidean lemma it is defined that if $p$ is prime then $$p|ab\Rightarrow p|a\lor p|b$$ How to prove by descending induction that if $$p|a^n \Rightarrow p|a $$ knowing that $a^n = a ...
1
vote
1answer
54 views

Does $a \uparrow \uparrow (n+1)-a \uparrow \uparrow n$ divide $a \uparrow \uparrow(n+2) - a \uparrow \uparrow(n+1 )$?

Does $$a\uparrow \uparrow (n+1) - a\uparrow \uparrow n$$ divide $$a\uparrow \uparrow (n+2) - a\uparrow \uparrow (n+1)$$ for all $a,n \ge2$ ? The case n = 0 is easy : $$a^a-a=a(a^{a-1}-1)$$ and ...
0
votes
1answer
70 views

Divisibility of prime numbers

I have this exercise in my worksheet in the discrete mathematics course.I don't understand the part that deals with prime numbers in integer-divisibility. "Show that for a prime number $p$, if a ...
1
vote
1answer
151 views

Finding equivalence classes

Consider the equivalence relation on Z x Z given by (m,n)R(p,q) if and only if mq = np 1) Find the equivalence class represented by (2; 5) 2) Describe the set S of the equivalence classes ...
1
vote
2answers
89 views

“Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
0
votes
2answers
46 views

Legality of doubly inductive proof requiring two base cases

I aim to show that the proposition $P_n$: "$11^n - 4^n$ is divisible by $7$" is true for all $n\in\mathbb{N}$. Assume that for some $n \ge 2$, $P_n$ is true. Then since \begin{align} 11^{n+1} - ...
1
vote
1answer
59 views

prove by induction that $n(n+1)(n+2)(n+3)$ is an integer multiple of $24$

prove by induction that $n(n+1)(n+2)(n+3)$ is an integer multiple of $24$ Let $P(n)$ be the proposition we want to prov, ie: $P(n):=24 \mid(n)(n+1)(n+2)(n+3)$ For $P(1)$ we have: $24 ...