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
3answers
70 views

Proof that $23^{n} - 1$ is divisible by $11$ for all positive integers $n$.

I'm having a bit of a problem proving this statement. Maybe someone can point me in the right direction? Best regards,
2
votes
2answers
34 views

Let $a, b \in \Bbb Z$. Consider the following function: $f : ℤ \times ℤ \to ℤ$ such that for any$ (x,y)\in ℤ \times ℤ, f(x,y) = ax + by.$

Let $a, b \in ℤ$. Consider the following function: $f : ℤ \times ℤ \to ℤ$ such that for any $(x,y)∈ ℤ \times ℤ, f(x,y) = ax + by.$ Fill in the blank in the following proposition with a simple ...
2
votes
2answers
60 views

$\gcd(x^2+1,x^2+4x+5)$

Is there anything I can tell about $\gcd(x^2+1,x^2+4x+5)$ for any given integer $x$? I believe I've seen similar questions in the past, though I don't remember any details or what to search for. I ...
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
7answers
593 views

If $\gcd(a, b) = 1$ then $\gcd(ab, a+b) = 1$?

In a mathematical demonstration, i saw: If $\gcd(a, b) = 1$ Then $\gcd(ab, a+b) = 1$ I could not found a counter example, but i could not found a way to prove it too either. Could you help me on ...
6
votes
2answers
191 views

Prove that the function $f(x,y) = ax + by$ is onto

I have been thinking about this problem for a while and have gotten stuck. This is a homework question so I just require some hints to push me to the answer. Question: Let $a, b$ be integers. ...
4
votes
3answers
88 views

Show that if $m,n$ are positive integers, then $1^m+2^m+\cdots+(n-2)^m+(n-1)^m$ is divisible by $n$.

Show that if $m,n$ are positive integers and $m$ is odd, then $1^m+2^m+\cdots+(n-2)^m+(n-1)^m$ is divisible by $n$. (Hint: Let $s=1^m+2^m+\cdots+(n-2)^m+(n-1)^m$. Obviously ...
1
vote
1answer
102 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$. ...
1
vote
2answers
80 views

combinatorics and divisibilty

in how many ways we can form a $8$ digit numbers from $1,2,3,4,5$ with repetition allowed & divisible by $8$. MY APPROACH : to be divisible by 8 : last 3 digit of the no. must be divisible by 8 ...
0
votes
1answer
32 views

Use the Euclidean Algorithm to show the gcd(56,72)|40

Use the Euclidean Algorithm to show the gcd(56,72)|40 How do I go about this since b is larger than a? Usually it is the other way around when I use the Euclidean Algorithm to find the gcd of a pair ...
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
4answers
119 views

Discrete math: proving gcd's and other fomulas

I have two questions: Suppose $a,b,s,t,u,v ∈ \mathbb{Z}$ such that $sa + tb = 21$ and $ua + vb = 10$. Show that $gcd(a,b) = 1.$ I feel like I'm going about this one in the wrong way. We haven't ...
1
vote
4answers
43 views

how do i prove $ab|n$ if $\gcd(a, b) = 1$ and $a|n $ and $b|n$?

Suppose that, for integers $a, b,$ and $n,$ $$\gcd(a, b) = 1\text{ and }a|n\text{ and }b|n.$$ How do I prove that $ab|n$ using linear Diophantine equations? Can I extend the above result to the ...
2
votes
2answers
54 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
1answer
46 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
3answers
38 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. ...
0
votes
2answers
114 views

Polynomial divisibility

Given $p(x) \in \mathbb Q[x] $ an irreducible polynomial, and $\alpha \in\mathbb C $ root of $p(x)$. Prove that if $q(x) \in \mathbb Q[x]$ it's a polynomial, such $q(\alpha) = 0$ then $p(x) \mid ...
0
votes
2answers
120 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
79 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
34 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 ...
2
votes
2answers
62 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
1answer
22 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
94 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 ...
0
votes
1answer
88 views

euclidean algorithm word problem

Mario has 773500 gold coins to purchase a number of stars and comets and each comet costs 208 gold coins and stars cost 299 coins.if the number of stars mario buys is at least twice the number of ...
0
votes
4answers
266 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 ...
0
votes
1answer
51 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
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 ...
2
votes
3answers
86 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
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, ...
0
votes
1answer
58 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
37 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
53 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
49 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
43 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 ...
1
vote
3answers
92 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
6answers
128 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 ...
7
votes
8answers
210 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 ...
4
votes
1answer
218 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
1answer
29 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) = ...
1
vote
4answers
47 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 :)
6
votes
5answers
278 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
-2
votes
6answers
197 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
40 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
3answers
84 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= ...
1
vote
2answers
53 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 ...
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...
4
votes
2answers
120 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
3answers
64 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 ...
2
votes
6answers
101 views

Prove that $4^{2n+1}+3^{n+2} : \forall n\in\mathbb{N}$ is a multiple of $13$

How to prove that $\forall n\in\mathbb{N},\exists k\in\mathbb{Z}:4^{2n+1}+3^{n+2}=13\cdot k$ I've tried to do it by induction. For $n=0$ it's trivial. Now for the general case, I decided to throw ...
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$. ...