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

Proving if $\gcd(c,m)=1$ then $\{x\in \Bbb Z \mid ax\equiv b \pmod m\} =\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$

Okay so I'm confused on how to approach this question. If $\gcd(c,m)=1$, then $S=T$ where $S=\{x\in \Bbb Z \mid ax\equiv b \pmod m\}$ and $T=\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$. I know ...
1
vote
2answers
25 views

Prove that $gcd(a, b) = gcd(a, b + ma)$?

How can I prove that gcd$(a, b)$ $=$ gcd $(a, b + ma)$? I have tried this: let $g = $gcd$(a, b) $, then $g$|$a$ and $g$|$b$. This means that $g$|$ax+by$. I don't know what to do next. Thanks.
1
vote
4answers
63 views

Prove that $(ma, mb) = |m|(a, b)$

I'm trying to prove that $(ma, mb) = $|$m$|$(a, b)$ , where $(ma, mb)$ is the greatest common divisor between $ma$ and $mb$. My thoughts: If $(ma, mb) = d$ , then $d$|$ma$ and $d$|$mb$ → $d$|$max ...
4
votes
2answers
98 views

Primes $p$ such that $p^2$ divides $x^2 + y^2 + 1$

Call a prime $p$ awesome if there exist positive integers $x$ and $y$ such that $p^2$ divides $x^2+y^2+1$. Observation: $2$ is not awesome, because $x^2+y^2+1\not\equiv 0$ (mod $4$). But $3$ is ...
2
votes
2answers
55 views

Suppose that $2^b-1|2^a+1$. Show that $b = 1$ or $2$.

I'm stuck with this one. I would appreaciate any idea how to prove this.
-1
votes
2answers
30 views

GCD or LCM confusion

Rosa is making a game board that is 16 inches by 24 inches. She wants to use square tiles. What is the largest tile she can use and how many square tile will be on her board? Need explanation on ...
6
votes
1answer
76 views

Bezouts Identity for prime powers

I have two prime powers $2^n$ and $5^n$ for some arbitrary $n$. Their gcd is $1$ but how do I get their integer linear combination which is $1$ in terms of $n$. In other words what will be the ...
0
votes
1answer
21 views

Number of positive $n$ s.t. $5|n^4 + 5n^2 + 9$

Find the total number of positive integers $n$ not more than $2013$ such that $n^4 + 5n^2 + 9$ is divisible by $5$. This problem was taken from Singapore Math Olympiad 2013, Open Section, First round. ...
4
votes
3answers
85 views

Why doesn't this calculation work?

I want to find some closed form for $\gcd(x^3+1,3x^2 + 3x + 1)$ but get $7$ which is not always true.
0
votes
3answers
24 views

Using long division on polynomials

Can anyone show me how to find $x^5 + 1$ divided by $x^3 + 1$? I tried using long division but I have that $x^3$ "goes into" $x^5 + 1$ about $x^2$ times but then I don't know how you're supposed to ...
2
votes
2answers
67 views

Prove that if $\gcd(ab,c)=1$, then $\gcd(a,c)=1$.

I was told to prove $\gcd(ab,c)=1$ then $\gcd(a,c)=1$. I picked a number $p$ that goes into $ab$ and $c$, so $ab=px$ and $c=py$. but now what?? I tried $abc=p^2xy$ but then I can't. Please help me!
1
vote
2answers
34 views

If $\exists$ $x,y \in \mathbb Z$ such that $ax+by=c$, then does $(a,b)|c$ or even stronger does $(a,b)=c$?

I think the first statement is true and the second statement is false. If so, I want to try to prove the first statement and find a counterexample (or proof) for the second. If $\exists$ $x,y \in ...
0
votes
2answers
61 views

Let $a$ and $b$ be positive integers and let $p$ be a prime number. Prove that if $a^p \equiv$ $b^p$ (mod $p$), then $a \equiv b$ (mod $p$).

I am trying to solve the following problem: Let $a$ and $b$ be positive integers and let $p$ be a prime number. Prove that if $a^p \equiv$ $b^p$ (mod $p$), then $a \equiv b$ (mod $p$). My attempt to ...
1
vote
1answer
26 views

Proof that there are at the most two numbers of exactly six digits that squared end with the same six digits

Written in a more formal way, proof that there are at the most $2$ numbers $n$ of six digits, that $$n^2 \equiv n \mod 10^6$$ Research effort: if $n^2 \equiv n \mod 10^6$ this means $10^6\mid ...
1
vote
1answer
31 views

Help with proving bezout's theorem?

Let $a,b,c\in\mathbb Z$ where $d=\gcd(a,b)$ and $c$ is a multiple of $d$. Suppose that $(x=x_0, y=y_0)$ is one particular integer solution to $$ax+by=c.$$ Then the complete set of integer ...
3
votes
3answers
103 views

how to prove if $m^{2}|n^{2}$ then m|n just hint please. [duplicate]

How to prove the following?: Let $m,n\in \mathbb{N}$ ; $ \;m^{2}\mid n^{2}\Longrightarrow \;\;m\mid n$ Just a hint please. I tried two ways but did not work.
0
votes
3answers
48 views

Number Theory: Remainders

“ Let $a, b \in \mathbb{Z}$ and that $0<a<b$. Given $b=qa+r$ where $0\leq r<a$. Prove that $r$ is always less than $\frac{b}{2}$. ” I have played around with several examples and have ...
4
votes
2answers
37 views

Find all the polynomials $p \in \mathbb R [X]$ such that $(x+1)p=(p')^2$

(Where $p'(x)$ is the derivative of $p(x)$) Research effort: what I thought is that given that $(x+1)|(p')^2$ then $(x+1)|(p')$ (I'd like to justify better this, but I don't know how) Then, ...
0
votes
1answer
18 views

A conjecture about the existence of a member within an interval with certain divisibility conditions - counter examples?

Conjecture The interval of the natural number line $[ap_{n}, (a+1)p_{n}]$ contains a member $e$ that is not divisible by any prime number $p_{m}$ less than or equal to $p_{n}$, if $(a+1) \leq ...
0
votes
1answer
68 views

An easy question with integer numbers

I have an easy question of arithmetic. Let $a, b, N$ be integer numbers such that $\mathrm{gcd}(a,b,N) = 1$. Is it true that there exists an integer number $x \in \mathbb{Z}$ such that ...
1
vote
1answer
36 views

Divisibility problem with product of two primes

Be $n=pq$ a natural number product of two different primes $p,q$. Prove, that on the set $\{1.2,2.3,...,n(n+1)\}$ there are exactly 4 numbers divisible by $n$.
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
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 ...
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 ...
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
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
42 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 ...
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$. ...
17
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
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
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
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 ...
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
93 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
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
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
85 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
51 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.