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)

9
votes
1answer
549 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
4
votes
1answer
110 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
4
votes
1answer
133 views

Solve $a^3 + b^3 + c^3 = 6abc$

Find solutions for $a^3 + b^3 + c^3 = 6abc$ in $\mathbb{N}$, such that $gcd(a,b,c) = 1$, except for $(1,2,3)$ and its permutations. Using trial and error I found out that if $a,b,c$ are solution ...
3
votes
1answer
222 views

Show that if $a$ and $b$ are positive integers then $(a, b) = (a + b, [a, b])$.

Show that if $a$ and $b$ are positive integers then $(a, b)=(a + b, [a, b])$. I was thinking that since $[a, b]=LCM(a, b)=\frac{ab}{(a, b)}$ that if $d= (a + b, [a, b])$, then $d|[a,b]$ and thus ...
3
votes
1answer
125 views

GCD of a subset

Let $A=\{i: 1 \leq i \leq n\} \subset \mathbb{N} $ and $B \subset A$, $|B|=k$ ($k < n$). What's the probability that $\gcd(B)>1$? EDIT: $n$ and $k$ are given. I think this can be solved with ...
2
votes
1answer
33 views

Biggest common divisor

Find the GCD of all the numbers from the set $$\{(n+2014)^{n+2014}+n^n\mid n\in \mathbb{N},n>2014^{2014}\}$$ Now I have the proof but i can't understand one thing Lets say $d$ is the GCD.Now let ...
10
votes
0answers
87 views

Curious number theory problem

$k,m,n\in\mathbb{N}$ satisfy $k^{m+n}=nm^n$. How can I show that $m=k$ and $n=k^k?$
8
votes
0answers
312 views

$f'/f\in\mathbb{Z}[[x]]$ for polynomials vs. formal power series $f$

I am curious about the following problem from MIT's Problem Solving Seminar (#26 here, though the link may stop working after a few weeks): Let $f(x) = a_0+a_1x+\cdots\in\mathbb{Z}[[x]]$ be a ...
6
votes
0answers
163 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
5
votes
0answers
35 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
5
votes
0answers
265 views

Natural extension of the divisor function $\sigma$ to the complex integers $\mathbb{Z}[i]$

The divisor function $\sigma$ of a positive integer $n$ is defined as the sum of the positive divisors of $n$. It turns out that this definition is equivalent to ...
3
votes
0answers
47 views

Generating all lesser numbers of two coprime numbers

Let's say I have two coprime positive integers, $a$ and $b$. How would you go about proving that it is possible to make all integers between 1 and $max(a,b)$ by subtracting them from each other? For ...
3
votes
0answers
193 views

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$. Hi there, I want to know if the following proof I have is strong enough, or if I'm making false assumptions :|. ...
3
votes
0answers
67 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 ...
2
votes
0answers
42 views

Proof relating to Euclidian Algorithm

The question is as follows: (1): Let m and n be positive integers with n < m and let r be the remainder when m is divided by n. Prove that $$r < \frac m2$$ (2): The Euclidean Algorithm for ...
2
votes
0answers
56 views

$27^{2004} + 22^{2004} - 4^{2004} - 1$ is divisible by (options)

(A) $299$ (B) $296$ (C) $298$ (D) $297$ This kind of sums are too problematic. Please provide a method which could give the correct answer in about a minute. :)
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 ...
2
votes
0answers
79 views

Fast check If the remainder is 1

Is there any fast method to 'say' that $R = (A \mod B)$ is $1$ or $R > 1$ or $R \neq1$ or $R > k>1$ ( where $k$ is a small integer on $32$ bits) without to actually calculate the real value ...
2
votes
0answers
53 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
2
votes
0answers
55 views

Prove that if $d_1=\gcd(a,b), d_2=\gcd(b,c), d_3=\gcd(c,a), D=\gcd(a,b,c)$, and $L=\operatorname{lcm}(a,b,c)$, then $L= \frac{abcD}{d_1 d_2 d_3}$

I tried to define: $a=d_1x_1$, $b=d_1y_1$; $b=d_2x_2$, $c=d_2y_2$; $c=d_3x_3$, $c=d_3y_3$. then $\operatorname{L.H.S} =d_1d_2d_3x_1x_2x_3=d_1d_2d_3y_1y_2y_3$ $\implies$ $x_1x_2x_3=y_1y_2y_3$; ...
2
votes
0answers
66 views

An upper bound on the least common multiple of the first $2n+1$ integers

Let $p$ be a prime number and let $a, n \in \mathbb{N}$. Then $$ p^a \mid \operatorname{lcm}(1, 2, \dots, 2n+1) \implies p^a \leq 2n + 1 \implies a \leq \dfrac{\ln(2n+1)}{\ln p}$$ and ...
2
votes
0answers
81 views

What is in common between decimals and reminder

I am trying to understand this solution for Project Euler' 26 problem. Could you please explain what do the decimals and remainders have in common? In context of this solution. Thank you in advance.
1
vote
0answers
27 views

find all the divisors of $6$ and $4+2\sqrt{5}$,then find $\gcd(6,4+2\sqrt{5})$

By inspection we see that the divisors of $6$ are $1,2,3,6$ For $4+2\sqrt{5}$ we have $4+2\sqrt{5}=2(2+\sqrt{5})$ showing that $\gcd(6,4+2\sqrt{5})=2$ Is this method correct; if not, how can I do ...
1
vote
0answers
37 views

Congruence equations

Given positive integer $Z, N$ and a set of positive integer $S$. Find smallest $k \in \mathbb{Z^+}$ such that $$a*k +1 \equiv Z \pmod N \ a\text{ is a positive integer that we don't know, and}\\ i*k ...
1
vote
0answers
97 views

Division of large numbers

Euclidean Algorithm Versus Horner Algorithm. I have come across this problem and I do not manage to find a good example for it. For all the numbers I pick there is no loss. Give an example of a ...
1
vote
0answers
53 views

Finding all positive integers $m,n$ such that $\frac{n^3+1}{mn-1}$ is an integer

Determine all ordered pairs $(m,n)$ of positive integers such that $\dfrac{n^3+1}{mn-1}$ is an integer. My work: $$\frac{n^3(m^3+1)}{mn-1}=\frac{(mn)^3-1}{mn-1}+\frac{n^3+1}{mn-1}.$$ Since, ...
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 ...
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. ...
1
vote
0answers
65 views

Prove that we always have $ 2n \mid \varphi(m^n+p^n) $

For each $ a ∈ \Bbb N^*$, denoted by $\varphi (a) $ is the number of positive integers not exceeding $a$ and coprime to $a$. Let $n, m, p ∈ \Bbb N^*, m \ne p$. Prove that we always have $2n \mid ...
1
vote
0answers
31 views

Computability of division of large numbers

What is the largest computable mathematical division in terms of the number of digits that can be handled by a typical desktop computer using the best available big number libraries, assuming input is ...
1
vote
0answers
135 views

K.K.T. conditions, Lagrangian gradient not defined for zero.

When I write the K.K.T. conditions for the problem I have, I get the following expression for the gradient of the Lagrangian: $$\frac{\partial \mathcal{L}}{\partial x} = - \frac{\sqrt{x} + ...
1
vote
0answers
149 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
0
votes
0answers
18 views

How to apply the generalised divisibility rule to numbers of the form $10^k+n$

This is kind of a long question but bear with me. There's actually a question mark at the end. I'm trying to apply the generalised (decimal) divisibility rules to numbers of the form $10^k+n$ where ...
0
votes
0answers
33 views

No prime number divides one

I was reading Euclid's theorem and came accross this affirmation but no prime number divides 1 Is there any mathematical proof or is it an axiom of number theory ? Can this affirmation be ...
0
votes
0answers
21 views

If p is a prime and p^a||n, prove that p does not divide the binomial coefficient n, p^a. Where || means exactly divides

I'm not quite sure how to use the fact p^a exactly divides n to do the proof.
0
votes
0answers
20 views

GCD and LCM Property

Let D = $\mathbb R + X\mathbb C[X]$ Show that $GCD(X, iX) = \mathbb R^\times$ and $LCM(X, iX) = \emptyset$ I have an outline of what to do but don't exactly know who to show all of it... First, ...
0
votes
0answers
28 views

Prove that $s \not= \emptyset $ by showing that at least one of $|a|$ or $|b|$ is an element of $S$.

. I'm trying to show an alternative proof to Bezout's Lemma (let $a, b \in \mathbb{Z}$, then there exists $x,y \in \mathbb{Z}$ such that $gcd(a, b) = ax + by$). Heres one of the steps in proving it: ...
0
votes
0answers
25 views

Is this division proof correct?

Show that if a is an even integer then 2 divides a. Let a be 2k 2/2k By Division Algorithm 2k=2q so k=q I'm not sure if this is the correct way to go about it so any insight helps. Thanks!
0
votes
0answers
70 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
0
votes
0answers
50 views

Natural numbers, a proof for the divisibility of any 3 given numbers?

I'm following EdX "Effective Thinking Through Mathematics" and they posed the following question: "If $x, y, z$ are natural numbers other than 1, and you multiply them together and add 1, ($x ...
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 ...
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 ...
0
votes
0answers
75 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
0answers
41 views

Distribution and upper bound of mimic numbers

Let the notation $ a\mid b $ denote ''$ a $ divides $ b $''. The mimic function in number theory is defined as follows [1]. Definition For any positive integer $ \mathcal{N} = ...
0
votes
0answers
30 views

Question about zero-divisors , rings and polynomials.

Let $i,n,m$ be positive integers. For every nonnegative integer $k<i+1$ , let $a_k$ be elements of a ring $A$ that satisfies : $1)$ The ring $A$ is isomorphic to ${\Bbb R}^{n}\times{\Bbb ...
0
votes
0answers
81 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
0
votes
0answers
236 views

Prove that $gx^2 \sim f$

Let $f(x,y) = ax^2 + bxy + cy^2$ be a positive semidefinite quadratic form with determinant $= 0$. Let $\operatorname{gcd}(a,b,c) = g$. Show that $gx^2 \sim f$. I'm not sure how to do this. All I ...
0
votes
0answers
184 views

Smallest positive integer divisible by and having digit sum equal to some 3-digit number.

Let $p,q,r$ be distinct digits among $1,2,4,6,8$, and consider the integer $pqr = 100p + 10q + r$. Let $N$ be the smallest positive integer that is divisible by $pqr$ and has digit sum equal to ...
0
votes
0answers
70 views

Fibonacci sequense, problem od division

How to show that $7\mid F_m\Longrightarrow 8\mid m$ and $4\mid F_m\Longrightarrow 6\mid m$, knowing that (I) Two consecutive terms in the Fibonacci sequence are relatively prime. (II) In ...
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 ...