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)

0
votes
3answers
30 views

Greatest common divisor of a number and the same number multiple of some rational

I want to simplify (e.g. in terms of prime factors and its exponents) given expression: $$ \gcd\left(a, a \frac{b}{c}\right), $$ where $c\mid ab$. Is it possible? Thanks!
1
vote
1answer
41 views

Finding the set {$ a\ |\ \mathrm{gcd}(a, b) = 1$}

I was wondering about the method to determine the set {$ a \ |\ \mathrm{gcd}(a, b) = 1$} : what is the faster way to get it ? I was thinking about to compute it like the sieve of Eratosthenes : test ...
1
vote
0answers
72 views

Any general hints on how to prove that two functions$\ f(n)$ and$\ g(m_1,m_2,…,m_{28})$ never have a common natural divisor?

All the variables are natural numbers. I'm not asking for a proof, since while we simply have$\ f(n)=n^3-n+1$,$\ g$ is a very long sum of cube roots (which contain square roots as well). I'm after ...
1
vote
2answers
24 views

How can I prove divisibility using congruence?

I'm new to this, so please excuse me if I said something wrong or offended anyone. We're doing the number theory in class, and I came across this question, which I had no idea how to even begin..: ...
0
votes
1answer
33 views

If and only If involving divisibility

If $a$, $b$, and $n$ are positive integers, prove that $a^n|b^n$ if and only if $a|b$. So far I've done one way of the proof... I've proved that if $a|b$, then $b=ak$, $k$ is an integer, then ...
2
votes
1answer
34 views

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$. proof: Suppose $\sigma(p^k) = [p^{k+1} -1]/(p-1) = n$. Then $n-1 = [p^{k+1} -1]/(p-1) - 1= [p^{k+1} -1 - (p-1)] /(p-1) = [p^{k+1} - ...
1
vote
1answer
42 views

Divisibility and Primes

Suppose that $p,q,r$ are prime numbers and $p$ is odd. If $p\,|\,(2q+r)$ and $p\,|\,(2q-r)$, prove that $q=r$. So I'm trying to use the definition of greatest common divisor to come up with two ...
1
vote
1answer
47 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
3
votes
4answers
56 views

Prove that $\gcd (n^3-1,n+1)=1$ for all even $n$.

Prove that if $n$ is even, then $$\gcd(n^3-1,n+1)=1.$$ I really don't have a clue with this one. Any help would be appreciated.
1
vote
3answers
63 views

Divisibility by primes

Suppose that $n$ is a natural number, $n \ge 2$, and $n$ satisfies: For each prime divisor $p$ of $n$, $p^2$ does not divide n. If $p$ is prime, $p$ divides $n$ if and only if $(p − 1)$ divides $n$. ...
1
vote
1answer
35 views

Fermat's Little theorem to find primes

Find $4$ primes that divide $14^{60} - 33^{60}$ okay, so the easiest thing to do was to re-write that as $7^{60}2^{60} - 11^{60}3^{60}$. However, that doesn't really help. Next step is the ...
0
votes
2answers
18 views

GCD(m,n) = sm + tn proof

Suppose that m and n are positive integers and that s and t are integers such that gcd(m,n) = sm + tn. Show that s and t cannot both be positive or both be negative. I understand that if both of them ...
-4
votes
1answer
63 views

Is 6m(2m +10) divisible by 4? [closed]

Is $6m(2m +10)$ divisible by $4$? What is the reason for this, assuming all variables are integers?
3
votes
3answers
97 views

when ${\rm gcd} (a,b)=1$, what is ${\rm gcd} (a+b , a^2+b^2)$?

I want to prove above statement "what is ${\rm gcd} (a+b , a^2+b^2)$ when ${\rm gcd}(a,b) = 1$" I've seen some proofs of it, but i couldn't find useful one. here is one of the proof of it. some ...
0
votes
5answers
48 views

Solving -2A - 2B = 2

I should know this, but when simplifying $$-2A - 2B = 2$$ When I divide the LHS by 2, do I divide -2A AND -2B or just one of them? I always thought you did one of them, and then the next. So order of ...
0
votes
6answers
60 views

Prove that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$.

I've come across the statement that if $\gcd (m,n)=1$ and $m\mid x$ and $n\mid x$, then $mn\mid x$. (This is needed for a proof of the correctness of RSA that I have been given.) I can't see how to ...
3
votes
2answers
71 views

How to explain why 10/0 is an okay grade book entry?

I usually record class grades in my grade book in a format like 9/10, where "9" means how many points a student earned and "10" means how many points they could possibly earn. The computer grade book ...
0
votes
1answer
16 views

N is a number in base 9.Find N when n is divided by 8(in base 10)?

N is a number in base 9.Find N when n is divided by 8(in base 10)? And N can be very large.say N=32323232.....50 digits This can be done by converting N to base 10.But time consuming. What will be ...
0
votes
2answers
45 views

If $c | ab$, then $c | a$ or$ c | b$

I need help proving/disproving the implication, If $c | ab$, then $c | a$ or $c | b$ So far, I got Assume $c | ab$ then $ab= cl$ for some integer $l$ Now what should my next step be?
2
votes
1answer
46 views

Divisibility Property

I am trying to justify the following result: Let $p,q$ be integers such that $GCD(p,q) = 1$. Then for all $n \in \mathbb{N}$ exists an integer $j_n$ such that $q^{j_n}t = t \ (mod \ p^{2n+1}), \ ...
0
votes
4answers
60 views

Is there a counterexample to “For all integers $a,b, d$, if $d\mid(3a+2b)$ and $d\mid(2a+b)$, then $d\mid a$ and $d\mid b$.”

I've tried to solve this problem, but I keep getting stuck at the end. Assume $a, b$ , and d are integers and $d$ $\neq$ 0. $3a+2b = dm,\,\,\,$ for some integer $m$. $2a+b = dn,\,\,\,$ for ...
3
votes
2answers
79 views

Divisibility property of $(a+b)^n-a^n-b^n$

Let $n$ be a natural number of the form $n=6k+1$ (while $k$ is a positive integer). Show that $(a^2+ab+b^2)^2$ divides $(a+b)^n-a^n-b^n$ for all integer numbers $a,b$ (such that $a^2+ab+b^2\ne0$).
2
votes
2answers
86 views

Find all primes of the form $2^{2^n} + 5$ for a nonnegative integer n

I'm a little lost on how to do this problem. It looks a lot like the definition for the Fermat numbers: $F_n = 2^{2^n} + 1$, however I'm not sure how to use that in order to find all of the primes of ...
1
vote
1answer
59 views

Divisibility !?? wihout mathematical induction if possible PLZ …

Hello I need to prove if $n\, |\, (x-a)$ and $n \, | \, f(x)$ then $n \, | \, f(a)$. It is true if $\operatorname{deg}(f)=1$ or $2$, but what for greater degree of $f(x)$? I don't know how to ...
0
votes
3answers
26 views

Divisibility involving exponents

How can one prove that $13$ divides $3^x - 16^x$ ? I have tried to apply some exponent laws but those only work when multiplying with the same base, not subtraction. Any helpful hints/advice would ...
4
votes
5answers
112 views

Show that $\gcd(a,b)>1$

Given are three natural numbers $a$, $b$ and $c$, for which $$\frac1a+\frac1b=\frac1c,$$ show that $\gcd(a,b)>1$. Could you someone provide a hint? I already tried algebraic manipulation, but ...
0
votes
1answer
21 views

Implications of a prime square dividing a binary quadratic form

Let $u,v$ be positive integers with $\gcd(u,v)=1$, let $k\ge 3$ be an odd integer, and fix a prime $p$. Now what are the implications of $p^2 \mid (u^2+kv^2)$? I know implications in certain cases, ...
2
votes
1answer
43 views

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$?

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$? I know that $\gcd(a,b) = 1$ means that there exist integers $m$ and $n$ such that $am + bn = 1$ Same thing for ...
0
votes
1answer
24 views

successive divisibility of a number by 9,8,7,6,5,4,3,2

There is a nine digit number . If you delete the digit at its unit place the remaining number would be divisible by nine, if you delete the digit at its tenth place the remaining number would be ...
0
votes
2answers
48 views

a proof of contradiction

I am wondering whether the following is a valid proof?
0
votes
1answer
42 views

Question about $\gcd$

Theorem: Let $K$ be an infinite field and let $L:=K(\alpha, \beta)/K$ be a field extension with $\alpha$ algebraic over $K$ and $\beta$ separable over $K$. Then $L = K(z)$ for a certain $z \in L$. ...
0
votes
2answers
15 views

Solve using Linear Congruences and Divisibility.

Let r be the common remainder when 1059, 1417 and 2312 are divided by d>1. Find the value of d-r. Find using linear congruences and divisibility.
10
votes
1answer
126 views

Does there always exist an even $m$ that is a multiple of exactly $n$ of the numbers $1$, $2$, …, $2n$?

Let $n>1$ be a positive integer. Then there exists a positive integer $m$ such that exactly half of the numbers $1$, $2$, $\ldots$, $2n$ divides $m$: one can take $m = (2n-1)!! = (2n-1) \times ...
0
votes
3answers
41 views

Modular arithmetic

Hello, What is the remainder when the following sum is divided by 4? $1^5 + 2^5 + 3^5 +...+ 99^5 + 100^5$ I feel like it has to do with modular arithmetic... I am trying to decompose every number ...
1
vote
3answers
51 views

Number of divisors of huge numbers

How many positive integers n are there such that n is a divisor of at least one of the numbers $10^{40}$,$20^{30}$? I'm having problems with this question. I know how to find the number of integers ...
2
votes
4answers
947 views

Find a 4-digit number which, divided by a 3-digit number (all unique digits) equals 9

This question is related to this Stack Overlow post. I tried following R code to find a 4 digit number divided by a 3 digit number (all unique digits) so that result equals 9: ...
0
votes
1answer
35 views

General Rule for calculating solutions to ax+by= 1 where (a,b)=1

A friend and I are in an intro to number theory class at UK and were struggling to prove the theorem that states that for two relatively prime integers $a$ and $b$ there exist integers x and y which ...
0
votes
3answers
38 views

How to prove $\gcd(a+m,b)=d$ when given $\gcd(a,b)=d$ and $b|m$?

some say I shall use $a+m-m$..... But I do not get it. Since $\operatorname{gcd}(a,b)=d$ then $a=q_1d$ and $b=q_2d$ And $b|m$ give $m= q_3b = q_3 q_2 d$ then $$a+m = q_1d+q_3q_2d = (q_1+q_3q_2)d$$ ...
2
votes
3answers
105 views

Prove or disprove $ p^{r+s}\mid q^{ke} - 1 \iff p^s \mid k$.

Let $p$ be an odd prime and $q$ be a power of prime. Suppose $e := \min\{\, e \in \mathbb{N} : p \mid q^e - 1 \,\}$ exists. Put $r := \nu_p(q^e - 1)$ (that is, $p^r \mid q^e - 1$ and $p^{r+1} \nmid ...
0
votes
4answers
44 views

The divisibility of the values of quadratic polynomials in $x$, for integer $x$

I would like to know method of finding validity of the statement by proofs. 1) $8$ does not divides $x^2 - 7$ for any integral value of $x$? 2) For any odd integer $x;$ the term $(x-1)^2$ is always ...
0
votes
3answers
42 views

Proof that the greatest common divisor of (a, a+2) is 2 if a is even and 1 if a is odd

Some help would be great on this, my teacher hasn't explained how to construct proofs to us, he just keeps doing them for us in class. I have at the beginning: Let a be even. Since the sum of two ...
0
votes
3answers
49 views

The only positive divisor of both $a$ and $a + 1 $ is $1$

Prove that if $a \in \mathbb Z$ then the only positive divisor of both $a$ and $a + 1$ is $1$. When I saw this statement I didn't understand it. The only way that I can see it being true is if a is a ...
1
vote
3answers
54 views

Part of a proof that the product of an odd and even integers is even

I'm practicing for a test on Monday and I'm trying to do some proofs - but I'm not entirely sure if this is sufficient enough for the question. "Prove that for all integers, m and n, if m is odd and ...
1
vote
3answers
99 views

Sum of the digits

Let $N$ be the greatest number that will divide $1305,4665$ and $6905$, leaving the same remainder in each case. Then what is the sum of the digits in $N$?
0
votes
1answer
54 views

Under what conditions can $a\sqrt{b} \pm c\sqrt{d}$ be written as $u+v\sqrt{w}$?

Let $a,b,c,d \ge 1$ be integers with $b$ and $d$ nonsquare and $a\sqrt{b} \ge c\sqrt{d}$. Now I have three related questions: Under what conditions can one find $u,v,w$ such that $a\sqrt{b} \pm ...
3
votes
1answer
52 views

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a.

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a. Any ideas? (Suggested proof by contradiction). Not really sure how to go about this.
0
votes
1answer
33 views

searching a number in 2D matrix

I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise. Finally i came across, this link ...
1
vote
0answers
21 views

Sequence terms being divisible

Here's a question I would like hints for: The sequence ${x_n}$ is defined by $x_{n+2}=6x_{n+1}-9x_{n}$ for $n \geq 0$ where $x_0=3$ and $x_1=18$. What is the smallest $k$ such that $x_k$ is ...
0
votes
0answers
28 views

Changing the zero product property and defining division by zero [duplicate]

I know that defining division by zero is not possible because it violates the zero product property we define, that is, $0\times a=0$ for every $a$. I wonder whether we can somewhat circumvent and ...
1
vote
7answers
90 views

Prove by induction that $n(n+1)(n+5)$ is multiple of 3

$$n(n+1)(n+5) = 3d$$ I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be ...