0
votes
1answer
32 views

Maximum value of function involving factorials

Define $$g_{(k,j)} = \frac{a^{n-k}b^k(k+n)!x^{k+n-j}}{k!(n-k)!(k+n-j)!}$$, where $n,k,j \in \Bbb{N}$ are fixed such that $(0 \leq x \leq a/b ),(b<a),(0 \leq k \leq n ),(2 \leq j \leq 2n),(0 \leq ...
2
votes
1answer
29 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
0
votes
0answers
26 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
3
votes
5answers
567 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
0
votes
1answer
40 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
1
vote
1answer
58 views

Polynomial producing only primes

The polynomial: $$a_n x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$$ Coefficients ai are natural numbers, the claim is once you substitute the positive integers 1,2,3,... for $x$ the values of the ...
1
vote
1answer
29 views

A relationship among multiple periodic arrays

There are N periodic arrays ai[n] with period Ti, respectively, where i=1, 2, … , N. Each array has a property that a[n]=1 when n=k*T where k is integer, otherwise a[n]=0. Then a new array is created ...
1
vote
2answers
30 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
-1
votes
1answer
34 views

$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
7
votes
4answers
5k views

What five odd integers have a sum of $30$?

I've been asked the following question: What five odd integers from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ that when summed together equals to $30$? Note that any integer can be used more than ...
1
vote
1answer
56 views

Number Theory Related Question: 3x^10=10x^3(mod13)

Number theory related question. Give all answers to: $$3x^{10}\equiv 10x^3 \pmod{13}$$ $0$ is obvious but I can't see a good way to draw out $12$. I've got this so far: Rearrange to ...
2
votes
1answer
82 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
23
votes
2answers
944 views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
4
votes
3answers
591 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?
6
votes
3answers
81 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
0
votes
0answers
31 views

Miller-Rabin primality test and testing one

I'm learning about Miller-Rabin primality test but in all the problems I see in the notes of a person I got them from, I see that even if he expressed the number as $2^1 \cdot something$, he still ...
0
votes
0answers
24 views

Taking the modulus of the power?

So I'm learning about Euler's theorem for reducing large powers modulo $n$ and what I'm wondering about is: can we simply take the modulus of a power of a number the same way we take it of the number ...
0
votes
1answer
18 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
0
votes
2answers
49 views

Find the smallest possible integer $k$ such that $8|7^{348}+2^{5605}+k$

$$ \text{Find the smallest possible integer } k \text{ such that } \\ 7^{348}+2^{5605} +k \text{ which is divisible by } 8 \text{ given that } $$ a≡b mod n⇒a^m≡b^m mod n okay, I understand that $a ...
1
vote
1answer
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$
1
vote
4answers
143 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.
2
votes
1answer
65 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 ...
0
votes
1answer
36 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 ...
0
votes
1answer
63 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$. ...
3
votes
3answers
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.
0
votes
1answer
69 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 ...
2
votes
2answers
131 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 ..
3
votes
1answer
46 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 ...
0
votes
2answers
98 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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
3answers
119 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$$
1
vote
8answers
194 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!!
1
vote
1answer
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 ...
12
votes
5answers
295 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$ ...
0
votes
5answers
81 views

$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 ...
2
votes
4answers
55 views

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?
1
vote
2answers
35 views

Prove $a,b \in \mathbb{Z}; p, q \in \mathbb{Z^+}$: If $a \equiv b \pmod{pq}\space \longrightarrow \space a \equiv b \pmod p$

$pq|a-b$ and $p|a-b$ $pql = a-b$ and $pk=a-b$ Let $k=ql$ then, $pql = pk=a-b$ First, is this correct? Second, if so, why can we let $k=ql$? How do we know $ql=k$?
1
vote
1answer
123 views

Diophantine equation $11\cdot 2^y-3x^{10}=2014$

Ok so I have a trouble figure out here For the Diophantine equation $11\cdot 2^y-3x^{10}=2014$, either find all integer solutions, or show that there are no integer solutions.
0
votes
1answer
46 views

Inductive proof for gcd

Proof that $(\forall n \in \Bbb N)[\gcd(n,(25n+1)^3)=1]$ By the inductive method: $p(n):\gcd(n,(25n+1)^3)=1$ $p(1): \gcd(1,26^3)=1 \implies p(n)\equiv \text{True}$ $p(n): $I assume that $p(n)\equiv ...
1
vote
1answer
46 views

Uniqueness proof of binary representation

I'm having trouble understanding this proof of uniqueness of binary representation of integers: Suppose there exists an integer $n$ with two different binary representations. Let these be: ...
1
vote
6answers
259 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
37
votes
6answers
4k views

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
1
vote
4answers
608 views

How many Positive integer solutions does the equation $x + y + z + w = 15$ have?

How many Positive integer solutions does the equation $x + y + z + w = 15$ have? Attempt: Let $x = m + 1, y = n + 1, z = o + 1, w = p + 1 $ Then, $ m + 1 + n + 1 + o + 1 + p + 1 = 15$ $ m + n + ...
0
votes
3answers
48 views

Find GCD $(10^6\times 6^2 \times 5 ; 6 \times 15 \times 3^7)$

Find GCD $(10^6\times 6^2 \times 5 ; 6 \times 15 \times 3^7)$ I have no idea.
0
votes
2answers
75 views

Solution to $x^2$ mod $23=7^2$ [duplicate]

Recently, I stumbled upon this problem, Solve $x^2$ $mod$ $23 = 7^2$, both here at MSE and somewhere surfing the web. I tried to solve it but don't know how. Although I can't remember where I found ...
2
votes
5answers
529 views

How many numbers must be selected from the set

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15 } to guarantee that at least one pair of these numbers add up to 16, explain your answer?
7
votes
9answers
1k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
0
votes
0answers
45 views

solve some discrete mathematic problems

(a) Solve for $x$ , $2x \equiv 5 \pmod 9$ (b) Prove that for any integer $a$, $a^2 \equiv 1 \pmod 4$ or $a^2 \equiv 0 \pmod 4$. (c) Prove that $a × b = \text{lcm(a, b)} × \text{gcd(a, b)}$ (d) ...