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)

0
votes
2answers
48 views

How can I prove this relation between gcd(a,b)?

I am stuck on starting this proof that involves gcd. Define $g_n=2^{2^n}+1$ and that $g_0g_1g_2...g_{n-1}=g_n-2$. Suppose that $a$ and $b$ are unequal positive integers. Prove that $gcd(g_a,g_b)=1$. ...
1
vote
1answer
33 views

Find all the $a$ such $539|a3^{253}+5^{44}$

This is what i thought: Given that $539|a3^{253}+5^{44}$ then $11|a3^{253}+5^{44}$ and $7^2|a3^{253}+5^{44}$ using congruences I get: $$a3^{253}+5^{44} \equiv 0 \pmod{7^2}$$ and ...
2
votes
2answers
184 views

how many pairs $(A, B)$ are there such that: gcd $(A, B) = A \oplus B$

Given an integer N,how can I find how many pairs $(A, B)$ are there such that: gcd $(A, B) = $A$ \oplus B$ where $ 1 ≤ B ≤ A ≤ N $. Here gcd $(A, B)$ means the greatest common divisor of the ...
4
votes
2answers
90 views

Prove that $3^{n+1}+3^n+3^{n-1}$ is divisible by $13$.

Prove that $3^{n+1}+3^n+3^{n-1}$ is divisible by $13$ for all positive integral values of $n$. I tried: $3^n \cdot 3^1+3^n+3^n\cdot\frac{1}{3}$ Then what should I do next? Help please?
2
votes
1answer
36 views

gcd's in non-UFD rings

In a UFD ring we have that for coprime $a,b \in R$, i.e. $(a,b)=1$: $$ a|cb \Rightarrow a|c $$ Does this property hold for non-UFD rings? I think not but do not recall a standard ...
2
votes
2answers
58 views

Number theory division proof, powers of 2

Ok, for some reason I'm getting stuck in what might be an easy question. Here's the problem: If a and b>2 are positive integers, prove that ${ 2^{a}+1 \over 2^{b} -1} $ is not an integer. My ...
1
vote
0answers
30 views

GCD among all possible sudoku matrix determinants

Today I came across an interesting question Consider a completely filled Sudoku, written as a $9 \times 9$ matrix. Show that the determinant of this matrix is divisible by $405$. The solution ...
2
votes
1answer
50 views

Self dual GCD/LCM identity in Landau's Elementary Number Theory

In Landau's Elementary Number Theory (Chelsea N.Y.) in Section 1, Chapter III, Problem 3 is the following self-dual identity: $$\gcd(\mbox{lcm}(a,b), \mbox{lcm}(b,c), \mbox{lcm}(a,c)) = ...
0
votes
2answers
60 views

Simple yet confusing: if $ f^2(x)=g^2(x)(x^2+1) $ then $gcd( f^2(x),g^2(x))=(x^2+1)$?

As mentioned in the title: f(x) and g(x) are polynomials above the Rationals field. if $ f^2(x)=g^2(x)(x^2+1) $ then does it mean that $ gcd( f^2(x),g^2(x))=(x^2+1) $? or maybe it isn't the ...
1
vote
0answers
35 views

If $a,b,c,d\in\mathbb N$ and $a^2+b^2\mid ac+bd$, can it be true that $\gcd(a^2+b^2,c^2+d^2)=1$? or $3$? or $74$?

If $a,b,c,d\in\mathbb N$ and $a^2+b^2\mid ac+bd$, can it be true that $\gcd(a^2+b^2,c^2+d^2)=1$? or $3$? or $74$? That problem is complicated. I've tried some approaches, but they're useless. ...
2
votes
1answer
112 views

Roots of $x^n - 1$ in an algebraically closed field of prime characteristic

Let $F$ be an algebraically closed field of characteristic $p$ , and let $n$ be a positive integer. Consider $ g := x^n - 1 \in F[x]$ Is it true that $ g$ has distinct roots in $F$ if and only if ...
1
vote
1answer
47 views

For given positive integers $n,k$ prove that there always exists some positive integer $x$ for which $2^n\mid \dfrac{x(x+1)}{2}-k$

For given positive integers $n,k$ prove that there always exists some $x$ for which $2^n \mid \dfrac{x(x+1)}{2}-k.$ My work: $\dfrac{x(x+1)}{2}$ is the sum of all positive integers upto $x$. Now, ...
2
votes
1answer
35 views

Number of factors of summation

Let $a(n)$ be the number of $1$'s in the binary expansion of $n$. If $n$ is a positive integer, show that $$\Bigg|\sum_{k=0}^{2^n-1}(-1)^{a(k)}\times 2^k\Bigg|$$ has at least $n!$ divisors. I think ...
2
votes
6answers
89 views

Proof that if $a^n|b^n$ then $a|b$ [duplicate]

I can't get to get a good proof of this, any help? What I thought was: $$b^n = a^nk$$ then, by the Fundamental theorem of arithmetic, decompose $b$ such: $$b=p_1^{q_1}p_2^{q_2}...p_m^{q_m}$$ with ...
0
votes
3answers
211 views

Show that if a, b and c are integers with c|ab then c|(a,c)(b,c)

Show that if a, b and c are integers with c|ab then c|(a,c)(b,c) Now (a, c) and (b, c) would both divide c since it's the gcd, but how would I show c divides their product, and (a,c)(b, c) $>=$ c ...
4
votes
1answer
53 views

Given an array of numbers and their gcd if one element is deleted how to get new gcd in minimum time

I have an array of numbers and their gcd if one element is deleted from the array then is it possible to get the new gcd without iterating over all the elements in the array. e.g the array is 3 6 6 ...
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$, ...
1
vote
5answers
63 views

Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.

Form the assumption, we can say $b=ak$ ,$k$ integer, $a=bm$, $m$ integer. Intuitively, this conjecture makes sense. But I can't make further step.
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
68 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.
4
votes
2answers
50 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
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
82 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!
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.
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 ...
1
vote
6answers
258 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 ...
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
92 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
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 ...
0
votes
4answers
110 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$$
0
votes
2answers
111 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
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 ...
1
vote
2answers
91 views

Integer division

I think I found a mistake in the princeton review "Cracking the GRE" 2014 edition on page 408. The problem is as follows: If $\frac{13!}{2^x}$ is an integer, which of the following represents all ...
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
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
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: ...
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 ...
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
40 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 ...
10
votes
4answers
240 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}$).
1
vote
5answers
123 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 ...
0
votes
0answers
38 views

Chinese reminder theorem - evaluating inverses

So, this is the CRT scheme I know: $$x=b_{1}*N_{1}*a_{1} + b_{2}*N_{2}*a_{2} + ...$$ Where $a_{x}$ is: $N_{x}a_{x} \equiv 1 (mod $ $n_{x})$ All right, so let's assume I have the following system ...
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 ...
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
2answers
68 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?
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
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$. ...