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

Sums and differences of distinct factors

Given $k, n \in \mathbb{N}$, let $\tau_{k}(n)$ denote the $k$th positive factor of $n$ in strictly increasing order. For example, $\tau_{1}(6) = 1; \tau_{2}(6) = 2; \tau_{3}(6) = 3; \tau_{4}(6) = 6$. ...
19
votes
5answers
1k views

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime?

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime? I don't mind if someone uses a different example, I want to learn how to prove this class of problems. My ...
0
votes
1answer
61 views

Greatest common divisor of $3$ numbers

Let $a,b, c$ belong to $\mathbb Z$ such that $(a,b,c) \neq (0,0,0)$. Define the [highest common factor] greatest common divisor ${\rm gcd}(a, b, c)$ to be the largest positive integer that divides $a, ...
2
votes
2answers
62 views

Proper decimal fraction for $\frac{4n+1}{n(2n-1)}$

Assume I have a function $f(n) = \frac{4n+1}{n(2n-1)}$ with $n \in \mathbb{N} \setminus \left\{ 0 \right\}$. The objective is to find all $n$ for which $f(n)$ has a proper decimal fraction. I know ...
0
votes
5answers
57 views

Find all integers $n$ (positive, negative, and zero) so that $n^2 + 1$ is divisible by $n + 1$.

I found $n=0, n=1, n=-2,$ and $n=-3$, but I am having trouble showing that these are the only four. I was thinking about maybe showing that no integer on the intervals $(-\infty, -3), (-3, -2), (-2, ...
0
votes
2answers
254 views

Find a pair of integers x and y such that 17369x + 5472y = 4

I'm doing discrete math. Been stuck on this problem forever. I need to find a pair of integers x and y such that 17,369x + 5472y = 4 I understand that I need to use the division algorithm. But what ...
1
vote
1answer
81 views

Problem with Diophantine equation

Let $a,b \in \mathbb N$ be coprime. Prove that for all $n\in \mathbb N$ such that $n>ab$ there are $r,s\in \mathbb N$ such that $n=ra+sb$. I'm really stuck on this problem. I know that since ...
1
vote
2answers
39 views

cancelling out before evaluation of variable

I'm been working on a theory, though my math is weak. Let's say I've managed to determine that I can arrive at an answer A by always using the formula BCD / D. Of ...
0
votes
1answer
32 views

Euclidean Algorithm in $\mathbb{Z}[w], w=\dfrac{1+\sqrt{-7}}{2}$

We are in the ring $\mathbb{Z}[w], w=\dfrac{1+\sqrt{-7}}{2}$. I am trying to find the gcd of 2-7 and 11. What I usually do is set up: 11=q(w-7) + r. I'll find q and r, then write: w-7=q(r)+r_new. ...
2
votes
2answers
98 views

How can I show that $a^n|b^n \Rightarrow a|b$

How can I show the following $$a^n|b^n \Rightarrow a|b$$ $$a^n|b^n \Rightarrow b^n=m \cdot a^n \Rightarrow b^n=(m\cdot a^{n-1}) \cdot a\qquad(1)$$ How can I continue? Do I maybe have to suppose ...
2
votes
2answers
68 views

Morphisms between $\mathbb{Z}/n\mathbb{Z}$ and $\mathbb{Z}/m\mathbb{Z}$

I'm trying to determinate how many morphisms of groupes exist between $\mathbb{Z}/n\mathbb{Z}$ and $\mathbb{Z}/m\mathbb{Z}$ for $n,m\in\mathbb{N}$. I know a morphism is determinated by the image of ...
0
votes
4answers
279 views

Why there aren't any squares of 2 divisible by 3?

A friend of mine recently told me that it is not possible to perfectly divide a cake in three pieces because 1/3 is an repeating decimal. Now, this is clearly a silly statement as 0.33333... is an ...
2
votes
2answers
47 views

Coprime Integers Proof Check

$\gcd(a,b)=1$ if and only if there is no prime $p$ such that $p|a$ and $p|b$ Prove it. So I went about doing it through contradiction: If $p|a$ and $p|b$ then $p|(x_{1})(x_{2})(x_{3})...$ where ...
0
votes
1answer
122 views

How to understand Apostol's proof of the irrationality of $\sqrt{n}$ if $n$ is not a perfect square?

Recently I am reading the textbook of Apostol, Mathematical Analysis, Second Edition. On page 7, there is a theorem 1.10: If $n$ is a positive integer with is not a perfect square, then $\sqrt{n}$ is ...
1
vote
0answers
114 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 ...
2
votes
3answers
121 views

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$. I could not approach the problem at all. I have no idea how to try the problem. Please help.
1
vote
0answers
86 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, ...
0
votes
1answer
61 views

Congruence of $n^n$ modulo 5

Given a integer $n$, determine the remainder of dividing $n^n$ for 5 in terms of an adequate congruence for n. So I'm really stuck in this exercise. By Euler little theorem I know $n^4 \equiv 1 ...
3
votes
3answers
42 views

Divisibility in base $7$ problem

Find all integers between $0 \leq a \leq 2400$ such they are divisible by $8$ and that their base 7 development has at least $3$ equal digits.
0
votes
3answers
58 views

Let $a$ and $b$ be relatively prime integers. Prove $a^2$ and $b^2$ are prime as well. [duplicate]

Prime means the greatest divisor of that number is $1$ and itself. But where do I go from here?
-1
votes
1answer
63 views

Prove that $1$ has only one divisor

I'm looking at Euclid's Theorem (the infinitude of primes). The standard proof assumes there are finitely many primes (and proceeds to contradiction). It involves $P :=$ the product of all the ...
2
votes
2answers
87 views

Using GCD/GCF to find number of intersections in a grid

The question I was trying to solve was: A rectangular floor $24×40$ is covered by squares of sides $1$. A chalk line is drawn from one corner to the diagonally opposite corner. How many tiles have ...
0
votes
1answer
33 views

Exercice whith primitive roots of unity and divisibility

For $n \in \mathbb{N}$, we define $\Phi_n \in \mathbb C[x]$ as the monic polynomial that has as roots the $n$th primitive roots of the unity. For example $\Phi_2 =(x+1)$, $\Phi_4 = (x-i)(x+i) = ...
7
votes
8answers
288 views

Proof of Divisibility of $n(n^2+20)$ by 48.

This is a question from Bangladesh National Math Olympiad 2013 - Junior Category that still haunts me a lot. I want to find an answer to this question. Please prove this. If $n$ is an even ...
1
vote
4answers
57 views

Problem on gcd of two numbers

Let $(a,b)$ be the Greatest Common Divisor of two numbers $a$ and $b$. Then, if $(r,n)=1$, is it true that $(r,n-r)=1$? If correct, prove it. Thanks in advance :)
1
vote
6answers
178 views

Prove that ${n^5 - n}$ is divisible by 5 [duplicate]

I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it. I am trying to prove it for several hours now, I started with ${n^5 - n} \mod 5 = 0$ but then I ...
1
vote
1answer
43 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
99 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
100 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
52 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
62 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
221 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
69 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
103 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
104 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
212 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
56 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 ...
5
votes
7answers
5k views

If gcd (a,b)=1 and gcd (a,c)=1, then gcd (a,bc)=1

How do I go about proving this? If gcd (a,b)=1 and gcd (a,c)=1, then gcd (a,bc)=1. I'm very confused with gcd proofs.
1
vote
0answers
75 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
67 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
71 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
1answer
58 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
153 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
53 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
46 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
120 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
259 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 ...