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
42 views

Perhaps similar number theory problems

I have this question: $n \in \Bbb N$. $n \geq 3$. Prove that $$ 1989\mid n^{n^{n^n}} - n^{n^n}$$ and also this question: Find the last five digits of $5^{5^{5^5}}$. What I saw that $1989 ...
1
vote
2answers
56 views

If I remove the premise $a\neq b$ in this question, will the statement still be true?

I encountered this proving problem, I can do the proof but my question is why in the condition/premise we need $a$ to be unequal to $b$? My guess is that even $a=b$, the statement is still true, is it ...
1
vote
3answers
96 views

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$.

Find all $n\in\mathbb N$, $n>3$ such that $p(n)=2n+16$, where $p(n)$ is the product of all the prime numbers less than $n$. E.g. $p(7)=2\cdot3\cdot5$ (and $n=7$ is a solution). Let ...
1
vote
3answers
95 views

Divisibility test for $4$

Claim: A number is divisible by $4$ if and only if the number formed by the last two digits is divisible by $4$. Here's where I've gotten so far. Let $x$ be an $(n+1)$-digit number. So $x= ...
0
votes
2answers
50 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$. ...
2
votes
3answers
51 views

Whats the formula to calculate width & height, when given a resolution and ratio

Let's say I have a puzzle, which says it has 1000 pieces. I also know it's a 4:3 ratio picture that I'm trying to put together. ...
-1
votes
6answers
217 views

What is the division of $1/0$? [duplicate]

It's approximate value, its infinite I know it but I want to know atleast the value upto $7$ decimal values.
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 ...
6
votes
1answer
68 views

Prove that no four positive integers $a, b, c $ and $d$ with $ab = 2d²$ can satisfy the equation $a² + b² = c²$.

Prove that : No four positive integers $a, b, c$ and $d$ with $ab = 2d²$ can satisfy the equation $a² + b² = c²$. Thank you...
2
votes
3answers
92 views

Show that if a is an odd integer and b is an even integer then (a,b)=(a,b/2)

Show that if a is an odd en integer and b is an even integer then (a,b)=(a,b/2) I understand that since a is not divisible by 2 but b is, the gcd of a,b also can't be divisible by 2 but I'm getting ...
4
votes
2answers
102 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?
4
votes
2answers
166 views

Generalization of “Sum of cube of any 3 consecutive integers is divisible by 3”

I have this question posted by professor in graduate Number Theory class. First he asked for proof that the sum of cube of 3 consecutive integers is divisible by 3, which is very easy to prove, but ...
2
votes
1answer
51 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 ...
1
vote
0answers
49 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
2answers
64 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 ...
2
votes
1answer
63 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)) = ...
1
vote
0answers
44 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
138 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
51 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
42 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
99 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 ...
4
votes
1answer
238 views

Divisibility of $2^n - 1$ by $2^{m+n} - 3^m$.

For what values of $m,n$ natural, do $2^n - 1$ is divisible by $2^{m+n} - 3^m$? Thank you very much.
0
votes
2answers
61 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 ...
4
votes
1answer
81 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
40 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
47 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
45 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
73 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.
0
votes
2answers
35 views

A formula for a sequence which has three odds and then three evens, alternately

We know that triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36... where we have alternate two odd and two even numbers. This sequence has a simple formula $a_n=n(n+1)/2$. What would be an example ...
1
vote
3answers
49 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
480 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
37 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
76 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
61 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
111 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
745 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
185 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
43 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
106 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
81 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
206 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
175 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
48 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 ...
2
votes
1answer
74 views

The factors of $5^n-3^n-2^n$

I have been assigned the following question. Let $f(n):= 5^n-3^n-2^n$. Prove that (a) $p$ divides $f(p)$ for each prime $p$; (b) $p^{k+1}$ divides $f(n)$ for $n=p^k$, with $p=2,3,5$ and ...
3
votes
6answers
213 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
35 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
91 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
68 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
48 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
51 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 ...