Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

0
votes
0answers
37 views

Determine the following set

Find the all the elements of the set $X = \{ n \in \mathbb N : a^n \ge (n +1)^b $} for fixed $a$ and $b$. $a,b \in \mathbb N \text{ and } 0 \in \mathbb N$ Since I am rather ...
2
votes
0answers
69 views

The n-envelope problem

This is original problem: You have n number of envelopes, and 100 $1 bills. you have to put these bills in the envelopes in such a way that any amount between 1 to 100 can be reached just by ...
1
vote
1answer
36 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 ...
0
votes
1answer
34 views

Is this number an integer, an irreducible fraction, or an irrational number?

I just want to know if I'm thinking correctly when I make these assertions: If u and v are positive integers with v > 1, and gcd( u, v) = 1, then: sqrt( u/v) is either an irreducible fraction, ...
4
votes
1answer
80 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
1
vote
1answer
58 views

For what values of $k\in\mathbb{N}$, $\sqrt{2^k+k^2}$ has integer solutions?

I'm looking for a rule giving integer solutions of: $$x=\sqrt{2^k+k^2}$$ for $k\in\mathbb{N}$. I found a solution for $k=6$, but I'm unable to find a general formula.
1
vote
3answers
65 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$ ...
1
vote
2answers
63 views

Proving the divisibility of large numbers without making large calculations [duplicate]

How would you you show that $2^{32}+1$ is divisible by $641$ without making large calculations?
3
votes
1answer
102 views

Showing that if $p$ is prime, then $(p^4 + 4)$ can't be prime

I want to show that if $p$ is prime, then $(p^4 + 4)$ can't be prime. I guess Fermat's little theorem may help, but I can't figure out how to use it for the proof. Can anyone point me in the right ...
7
votes
2answers
115 views

I’ve just noticed something interesting! If $(a, b,c)$ is a Pythagorean triple with $b, c$ consecutive integers then $c \mid a^b – 1$, proof/disproof?

Here are some examples: $(3, 4, 5)$ is a Primitive Pythagorean Triple (PPT), $3^2 + 4^2 = 5^2$, where $4$ and $5$ are consecutive integers. $(3^4 – 1)/5 = 80/5 = 16$ $(5, 12, 13)$ is a PPT, $5^2 ...
1
vote
0answers
67 views

Show that $q \equiv 1 \mod p$…

The problem: If $p$ is a prime and $q(\neq 2)$ is a prime divisor of $2^p-1$, then $$q \equiv 1 \mod p$$ Sorry about deleting my other work guys. I messed up when trying to re-post. My ...
7
votes
1answer
88 views

Mediteranean Mathematics Olympiad 2014 number theory problem.

I paraphrase it slightly to make it shorter. Prove for every integer $S\geq100$ there exists a positive integer $P$ such that there are at least two different solutions in positive integers(up to ...
3
votes
3answers
65 views

Prove that there exists $s$ such that $s(ab-1)^n +1$ is composite

I find this interesting question in a number theory book. Given two positive integers $a, b$ such that $a>1, b>1, \gcd(a, b)=1$. Prove that there exists a positive integer $s$ such that ...
0
votes
0answers
37 views

What is the remainder of this big number without doing major calculations?

I am solving a problem and came across a situation where to calculate remainder for big values with out doing major calculation. In my case I need to compute the expression: $$2^{n}-1+k ...
1
vote
2answers
185 views

Solutions to the Mordell Equation modulo $p$

It is well known that the Mordell Equation $x^2 = y^3 + k$ has finitely many solutions, but has solutions modulo $n$ for all $n$. One proof of this involves using the Weil Bound to show that $x^2 = ...
1
vote
1answer
44 views

Show $(2^m-1,2^n+1)=1$ if $m$ is odd [duplicate]

Let $(2^m-1,2^n+1)=1$ and suppose $m$ is even. Also, $m,n,k\in \mathbb{N}$. We have $$(2^{m}-1)x+(2^n+1)y=1$$ $$(2^{2k}-1)x+(2^n+1)y=1$$ $$(2^{2k}-1)y\equiv 1\pmod{2^n+1}$$ $$(2^k+1)(2^k-1)y\equiv ...
4
votes
2answers
41 views

Let p, q be prime; if p | q + 1 then also p | q^(q + 1) + q, proof?

Let $p$, $q$ be prime. if $p | q + 1$ then $p | q^{q + 1} + q$ Any elementary proof will be appreciated!
2
votes
1answer
27 views

Why does $x^{m \cdot 2^i} \equiv -1$ with odd $m$ imply that $x$ has order $m \cdot 2^{i+1}$?

It is clear that $$x^{m \cdot 2^{i+1}} \equiv 1$$ for odd $m$ but is there a theorem or an obvious reason why $x$ cannot have order smaller than $m \cdot 2^{i+1}$? Context: I am trying to understand ...
0
votes
2answers
24 views

Can we say If q is incongruent to p modulo n then $q\equiv -p$ (mod n)

Am I right to write: If q is incongruent to p modulo n, then $q\equiv -p$ (mod n) Thanks for helping
1
vote
3answers
44 views

If $p, q$ are prime and $p > q$, then $p|(p – q)^p + q$, proof?

Can anyone give an 'elementary' proof?
1
vote
3answers
39 views

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

As stated in the title, the problem to prove is Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$. I think I've proved it, but I would like a second opinion. Here ...
0
votes
1answer
50 views

fastest algorithm for prime factorization [on hold]

I need the fastest algorithm to factorize the given number $N$ as a product of primes. $$N=p_1^{e_1}p_2{e_2}\ldots p_n^{e_n}$$ where $p_1, p_2,\ldots ,p_n$ are primes and $e_1,e_2,\ldots, e_n$ are ...
2
votes
1answer
46 views

suppose $\omega(n)$ denote the number of distinct prime factors of n

Suppose $\omega(n)$ denote the number of distinct prime factors of n. Prove that$$|\mu(n)|=\sum_{d|n}\mu(d)*2^{\omega(n/d)}$$ Can any one give me some hints about this problem? Is $\mu(n)$ a ...
2
votes
1answer
26 views

A Möbius Identity

I need to prove the identity $$\sum_{k = 1}^n \mu(k)\left[ \frac{n}{k} \right] = 1$$ where $n$ is a natural number, and $[n]$ denotes the floor function. The proof also should not use the Möbius ...
1
vote
2answers
42 views

Help with proof regarding degrees of polynomials

How do you prove that if $f(x)\mid g(x)$ in $F[x]$, then either $g(x) = 0$ or $\deg(g(x)) \geq \deg(f(x))$ I'm not really sure how to prove these types of statements
-1
votes
0answers
38 views

How does this method work? [on hold]

Let $n=16$ for an example: step 1: get set of prims from $1$ to $\sqrt{2n}: \{2, 3, 5\}$, step 2: get set of $n \mod 2, n \mod 3, n \mod 5: \{0, 1, 1\}$, setp 3: from $0$ to $n-3$, ...
2
votes
2answers
56 views

is a given expression an irreducible fraction

The following statement is pretty obvious: ...
1
vote
2answers
46 views

Discrete Mathmatics Proof

Here is the question: $a$ and $b$ are any two integers. $c$ is any prime. Prove that if $c$ divides $ab$, then $c$ divides $a$ or $c$ divides $b$ (or both, as in it can divide either or both, i.e. ...
1
vote
1answer
28 views

Explanation of key point of Lagrange 4-square theorem

I was reading the following article about Lagrange's 4 square theorem: http://en.wikipedia.org/wiki/Lagrange's_four-square_theorem#The_classical_proof Where in the 3rd paragraph of the classical ...
2
votes
0answers
26 views

Polynomial Density Theorem

So I was consider Lagrange's 4-square theorem and came up with this generalization: Given a polynomial with rational coefficients $$P(x) = a_0 + a_1x + ... + a_nx^n$$ Determine if there exists ...
3
votes
2answers
42 views

Proving $\frac{p-1}{2}!\equiv (-1)^t$ where $t$ is the number of integers which are not quadratic squares

Prove that $\frac{p-1}{2}!\equiv (-1)^t$ where $t$ is the number of integers $0<a<\frac{p}{2}$ which are not quadratic squares $\pmod p$ ($p\equiv3\bmod4$) I don't know really from where ...
0
votes
0answers
22 views

Fermat pseudoprimes p to base 2 (AKA Sarrus or Poulet numbers) with special properties

Are there any known Fermat pseudoprimes $p\;$ to base $2\;$ (Sarrus or Poulet numbers) with the properties $q = (p-1)/2\;$ is prime and $p \equiv 0 \pmod 3?$ I was not able to find any example up to ...
1
vote
0answers
61 views

Is the repeating decimal $0.999… \in \,(0, 1)$? [duplicate]

Is the repeating decimal $0.999.... \in (0, 1)$? It seems like it can't be as $0.999...$ is defined as being equal to $1$.
2
votes
3answers
51 views

What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one. PS : The numbers are just for example. There may be the same question for BIG numbers. ...
1
vote
1answer
26 views

Show $(a+b, a-b) = 1$ or $2$ if $(a,b)=1$ [duplicate]

Here was my take on the proof. We already know that since $(a,b)=1$, there exist integers $x,y$ such that $ax+by=1$. Let $d=(a+b,a-b)$. Then $d|(a+b)$ and $d|(a-b)$. In particular, there exist ...
1
vote
0answers
49 views

Finding the number of elements in $\left(ℤ[i]\right)_m$

If $m$ = $m_1$ + $m_1i$ ∈ $ℤ[i]$, is there a general formula to find the number of elements in $\left(ℤ[i]\right)_m$?
0
votes
0answers
24 views

What are the patterns in the number of divisors $d(n)$ of the highly composite numbers?

I am trying to understand the patterns in the number of divisors $d(n)$ of the highly composite numbers. The numbers marked with an asterisk are the superior highly composite numbers. The first ...
2
votes
2answers
85 views

A transcendental number from the diophantine equation $x+2y+3z=n$

Let $\displaystyle n=1,2,3,\cdots.$ We denote by $D_n$ the number of non-negative integer solutions of the diophantine equation $$x+2y+3z=n$$ Prove that $$ \sum_{n=0}^{\infty} ...
1
vote
2answers
29 views

Word problem regarding system of linear congruences…

Full problem: A hoard of gold pieces ‘comes into the possession of’ a band of 15 pirates. When they come to divide up the coins, they find that three are left over. Their discussion of what to ...
3
votes
3answers
49 views

Counting the factors of $2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$

Let $n = 2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$. How many natural-number factors does $n$ have? I'm not quite sure how to go about solving this problem; there seems to be a lot of overcounting involved.
0
votes
1answer
19 views

Solving this system of linear congruences…

Just wanted to see if I did this correctly. We have $$3x \equiv 1 \mod 5$$ $$2x \equiv 6 \mod 8$$ Observe that our second congruence can be divided by 2, so we then have $$x \equiv 3 \mod 4$$ ...
1
vote
2answers
17 views

Perfect square and odd prime divisor

Show that the number of distinct remainders which occur when perfect square is divided by an odd prime $p$ is $\frac{p+1}{2}$. I expressed the square number using Euclid's lemma of division but I ...
0
votes
0answers
30 views

Prove that $l = k/\gcd(m,k)$.

Suppose $ml = kt$ where $t$ is an integer and $m<k.$ $\implies k~|~ml$ $~~~~~$and $~~~~~$ $1 \leq \gcd(m,k) \leq m$ $\implies \dfrac{k}{\gcd(m,k)}~\Big|~\left(\dfrac{m}{\gcd(m,k)}\right)l$ ...
6
votes
2answers
131 views

Why do all multiples of 99 have a digit sum $\geq 18$?

I noticed that this seems to be the case while looking at some multiples. Q: Can someone come up with a positive conterexample or show that there can't be one?
1
vote
1answer
28 views

Square of $7+\sum_{k=1}^n6\times10^k$ [duplicate]

If we build a number as follow: $$N=7+\sum_{k=1}^n6\times10^k$$ we find: $$N^2=9+\sum_{k=1}^n8\times10^k+\sum_{j=n+1}^{2n+1 }4\times10^{j}$$ that means for example: $67^2=4489$, $667^2=444889$, ...
0
votes
2answers
24 views

Divisibility crieteria

This is a follow-up question. The problem is: Given two natural numbers, $m$ and $n$, and $n \vert m^2$. Find necessary and sufficient conditions for $n \vert m$. Here are what I find: ...
0
votes
1answer
38 views

Find $x$ such that $o_1^x-o_2^x \neq 2(o_3^x-o_4^x)$ where $o_i$ is an odd number, $o_1>o_2$, $o_3>o_4$ and $x$ is a positive integer

A few hours ago I asked this question. This problem came up while working on a graph labeling problem. I already have a exponential algorithm working. But I want to further reduce the complexity. ...
0
votes
3answers
55 views

Prove that $n^2 + 1$ is not a multiple of $6$ for any positive integer $n$

Prove that $n^2+1$ is not a multiple of $6$ for any positive integer $n$. I i think prime factorization would be a good way to go about this problem but I need some help.
1
vote
4answers
101 views

Find odd numbers $(o_1,o_2,o_3,o_4)$ such that $o_1^2-o_2^2=2(o_3^2-o_4^2)$ such that $o_1>o_2$ and $o_3>o_4$

I am working on a graph labeling problem and am stuck at the following problem on odd numbers. Find (all) odd numbers $(o_1,o_2,o_3,o_4)$ such that $o_1^2-o_2^2=2(o_3^2-o_4^2)$ such that $o_1>o_2$ ...
1
vote
0answers
50 views

Given $m^k\le n <m^{k+1}$ find $x$ and $y$ such that $x\cdot m^k+y=n$

Let $n,m,k\in\mathbb{N}$. Assume $m^k\le n <m^{k+1}$. Find $x,y\in\mathbb{N}$ such that (1) $x\cdot m^k+y=n$ (2) $0<x<m$ (3) $0\le y<m^k$ My question: does there exist a general ...