# Tagged Questions

37 views

### A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$\sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right)$$ and looking for a way to ...
58 views

### prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
44 views

### fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
70 views

### prove/verify prime division

$a_i$ positive integers for $1\le i\le n$ if $p$ prime and $p\mid a_1a_2\cdots a_n$ then $p\mid a_i$ for some $1\le i\le n$: My thinking is to prove it by contraposition. $p$ does not divide ...
39 views

### Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response: Prove that there's no ...
28 views

### Bézout's identity Application

I am trying to prove the following lemma: Let $n,m$ be positive integers, and let $d = GCD(m,n)$. Let $c,r$ be positive integers s.t. $d = cm - rn$ If $c > dn$, then for every two positive ...
68 views

### Introductory Induction Proof

I am in currently in a discrete mathematics class, and I've done well on every problem I've encountered. Unfortunately, I find myself weak at some of the seemingly straight forward induction problems. ...
26 views

### Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
146 views

### Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
51 views

### Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
70 views

### Prove that $17$ divides $9a + 5b$

So, according to the book, for all $a, b, c$ that are elements of integers, it holds that $a|b$ implies $a|bx$ for all $x$ that is an element of integers. In other words it works for all ARBITRARY $x$ ...
35 views

597 views

### Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
82 views

43 views

### Show that $gcd(a,b) |d$ and hence $gcd(a, b) \leq d$, where $d$ is the smallest number of the form $ma+nb$

Show that if $d$ is the smallest element in the set $S = \{s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb \}$ such that $d = ax + by$ then $\gcd(a,b) |d$ and hence $\gcd(a, b) \leq d$
147 views

### What's the easiest way to factor $5^{10} - 1$?

What's the easiest way to factor $5^{10} - 1$? I believe $5 - 1$ is a factor based off the binomial theorem. From there I do not know. We are using congruence's in this class.
68 views

### Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
37 views

### Help with understanding Induction proofs

From my understanding, to prove induction problems, we must: Find a base case Assume n=k holds true Prove n=k+1 with the assumption However I am looking at the proof of a problem and they don't ...
67 views

### Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

I am studying the solution to a problem: Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$. ...
109 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.
72 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 ...
134 views

### Prove that if $a$ is irrational then $\sqrt a$ is irrational

Just hints but solution thx. Any hints for me? I simply suppose that $a = \dfrac mn$ then $\sqrt a = \sqrt{\dfrac mn}$ But this does not make sense ..
47 views

### $k$th difference of $1,2^k,3^k,…$

I read, in an exposition of Euler's proof of Fermat's theorem on sums of squares, that the $k$-th order finite forward difference of the function $f(x_i)=x_i^k$, relatively to the nodes $x_i=i$ where ...
101 views

### decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
84 views

### Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
35 views

### showing that encryption method is bijective

A encryption method relates a letter Ω to letter $Δ\equiv aΩ + d$ $(mod 30)$ with $a, d\in {\Bbb N}$. Each letter relates to a number: A = 01, B = 02, C = 03 ... i. Show, that this encryption method ...
120 views

### Greatest common divisor. Help [closed]

Let $n \in \mathbb{N}$. Prove that $$\gcd(2^n+7^n;2^n-7^n)=1$$ $$\gcd(2^n+5^{n+1};2^{n+1}+5^n)=3\text{ or }9$$
226 views

### How to find all the positive integral solutions of $5x+7y=100$?

How to find the number of all the positive integral solutions and the solutions itselves of $$5x+7y=100?$$ Please help me!!
42 views

### Sum of floor of rational product

Given natural numbers $a,b,n$, where $a<b$, $n<b-1$, and $a$ and $b$ coprime, Find a closed form for the sum: ${\displaystyle \sum_{k=1}^n \left\lfloor k \frac{a}{b} \right\rfloor}$ We know ...
307 views

### How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
### $4011x+42053 \equiv 2x-782398 \pmod {10}$
$4011x+42053 \equiv 2x-782398 \pmod {10}$ $10|(4011x+42053-2x+782398) \space \rightarrow \space 10|(4009x + 824451)$ $\rightarrow\space 4009x\equiv -824451 \pmod {10}$ I am dubious about this next ...
### Find the smallest positive $n$ such that $n! \equiv 0 \pmod {425}$
By exhaustion I found $n=17$, but in trying to solve this I can only see that: $$425\space |\space n!\space \longrightarrow\space 425k=n!$$ Any hints?