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)

6
votes
0answers
76 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 ...
6
votes
0answers
177 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
297 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
75 views

Prove the equality

Given $a,b,c,d$ are positive integers such that $a^2+b^2+c^2+d^2-ab-bc-cd-da$ is divisible by $abcd$. Prove that $a=b=c=d$.
3
votes
0answers
50 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
273 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
76 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
25 views

Prove the congurence

I am looking for a proof of Gauss's generalization of Wilson's Theorem. Let $S$ be the set of all the integers which are less than and mutually prime to $n (>4)$ (not of the form $p^\alpha$, ...
2
votes
0answers
44 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
60 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
67 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
81 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
57 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
80 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
95 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
33 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
1
vote
0answers
47 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
1
vote
0answers
33 views

Find the Conditions

Let $a, b, c, d, r, s \in \mathbb{N}$. Find the necessary and sufficient conditions under which $r \mid (a-b)$ and $s \mid (c-d)$ $\implies$ $\operatorname{lcm}$ $(r,s)\mid(ac-bd)$. A little ...
1
vote
0answers
51 views

Showing DO NOT exist GCD of $6$ and $2+2 \sqrt{-5}$ in $\Bbb Z[\sqrt{-5}]$.

Showing DO NOT exist gcd of $6$ and $2+2 \sqrt{-5}$ in $\Bbb Z[\sqrt{-5}]$. I tried it. Suppose $d$ is GCD of $6$ and $2+2 \sqrt(-5)$. then there exist $x,y \in \Bbb ...
1
vote
0answers
14 views

Efficient way needed

Given N, M find the : GCD(1, 1) * GCD(1, 2) * … * GCD(1, M) * GCD(2, 1) * GCD(2, 2) * … * GCD(2, M) * … * GCD(N, 1) * GCD(N, 2) * … * GCD(N, M) modulo 10^9+7 Constraints: 1 <= N, M <= 2 * ...
1
vote
0answers
27 views

Using $ \gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$ for GCD?

It should be true that $\gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$. But: How can I use this equality to compute the GCD of $a$ and $b$? It seems as if $r$ is of the form $r = k\cdot b + s$ ...
1
vote
0answers
34 views

GCD of this polynomial

So here is the exact question that i am having trouble on: "Extend the Euclidean algorithm to polynomials and find the greatest common divisor of: $3x^5-10x^4-4x^3-14x^2-7x-4$ and ...
1
vote
0answers
30 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
39 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
109 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
72 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
45 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
42 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
56 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!
1
vote
0answers
67 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
33 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
146 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
153 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
74 views

Counting maximum moves

Given two arrays, each of size N denoted by A1,A2...AN and B1,B2...BN. Let us maintain two sets S1 and S2 which are empty initially. In one move ,Pick a pair of indexes (i, j) such that : ...
0
votes
0answers
40 views

divisibility question involving primes

I have a question concerning the following divisibility problem. For any prime $p$ we define set: $\mathtt{V_{p}}:=\Biggl\{F\in\Phi\Biggl|\begin{cases}p^2\nmid ...
0
votes
0answers
54 views

Finding an asymptotic formula for $f(m,n)=\sum_{\substack{d\mid m \\ d\leq n}}1$?

$$f(m,n)=\sum_{\substack{d\mid m \\ d\leq n}}1$$ Here $n<m$ and $m$, $n$ are positive integers.
0
votes
0answers
31 views

Let $f(x)\in K[x]$ ($K$ field). Prove that if $(f(x),f´(x))=1$ (greatest common divisor is 1) then $f(x)$ does not have multiple roots in $K$

Please I would like you to tell me if my proof is correct Let $f(x)\in K[x]$ ($K$ field). Prove that if $(f(x),f´(x))=1$ (greates common divisor is 1) then $f(x)$ does not have multiple roots in $K$ ...
0
votes
0answers
68 views

Among the superior highly composite numbers, which are the most divisor dense numbers?

I’m searching for the most divisor dense natural numbers. Firstly we have the highly composite numbers: 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, … But ...
0
votes
0answers
56 views

Vieta jumping with non-monic polynomials

I have recently discovered Vieta jumping as a problem-solving technique. In order to teach myself about it, I have located most (all of?) the standard references, both here on MSE and "out there" (via ...
0
votes
0answers
36 views

Moving up the Y axis the lengh of the hypotenuse of a right triangle

If i have a right triangle ABC with B being the right triangle and length AB = 50 and length BC = 50. Based on the Cartesian coordinate system if i wanted to move up the Y axis the length of the ...
0
votes
0answers
34 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 ...
0
votes
0answers
17 views

WordProblem on factors and remainder theorem

Mr.Chaalu while travelling by Ferry queen has travelled the distance one Kilometer more, than the fare he paid per km. Initially he had total amount of Rs.350/- in his wallet. Now he is only left with ...
0
votes
0answers
11 views

Showing that s'm is a common multiple of m and n

so in class teacher gave us this algorithm GCD(m,n)=GCD(n mod m, m). after that we used it to find s and t. for example we found GCD of 453 and 174 and their s and t by making a table like this ...
0
votes
0answers
26 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
31 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
31 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
77 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
61 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
45 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 ...