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

learn more… | top users | synonyms

1
vote
1answer
27 views

Even number being express as $4q$ or $4q+2$

Prove that every positive even integer $n$ can be expressed as $n=4q$ or $n=4q+2$, $\forall q\in Z$. I expressed $n$ as $n=4q+r$ using Euclid's lemma and I have been able to prove that $n=4q+0, ...
-5
votes
0answers
52 views

The abc-conjecture is true??? [on hold]

A strong version of the abc-conjecture maybe formulated as follow: there are no triples of coprime positive integers $a+b=c$ such that $c>d^{1+\epsilon}$ since ...
1
vote
3answers
62 views

Product of two negative numbers is positive [duplicate]

What is the practical proof for $-1(-1)=+1$. Actually multiplication is repetitive addition. I am struggling how can I provide an activity to prove practically $-1(-1)=+1$
-4
votes
0answers
61 views

The Erdos-Straus Conjecture and The Sierpinski Conjecture [on hold]

Sierpinski states that for all integer $n>1$ there exists $a,b,c$ such that $$\frac{5}{n}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}.$$ The conjecture is true for all cases where $a=b$ and $n=c=2a,$ ...
2
votes
1answer
36 views

If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
0
votes
0answers
18 views

A question related to the Descartes-Frenicle-Sorli conjecture on odd perfect numbers

Good day to everyone! I apologize in advance for the somewhat long post, but I had to put in all the details into a single question to communicate what I believe to be a viable approach to odd ...
2
votes
4answers
130 views

Find all $n$ for which $2^n \ge (n+1)^2$

Find all of the elements of $X= \{ n \in \mathbb N: 2^n \ge (n+1)^2\}$ Could someone give me a hint to nudge me in the right direction?
1
vote
0answers
22 views

Lowest sum of 2 sets of number pairs

I am given a set of unique integers $n$. I need to compute the smallest sum $s$ such that there are two different pairs of integers $(x1, x2)$ and $(y1, y2)$ where $x1 < x2$ and $y1 < y2$ and ...
0
votes
0answers
22 views

Proof of convergence of Kaprekar's Constant

I've tried googling this one a bit but nothing seems to come up, even though its considered to be a well known fact. Why does the kaprekar process of taking a 4 digit number: L, generating L' and L'' ...
1
vote
5answers
73 views

finding mod of an expression with variables

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 (\bmod 6)$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 (\mod 2)$ so ...
0
votes
1answer
24 views

Converting infinite base-k expansions into base-j expansions

I understood the method of transforming a finite sized base-k numbers to another base (j) through the use of successive divisions For example $$12_{10} = 12/2 + 0*2^0 = 6/2 + 0*2^1 + 0*2^0 = 3/2 + ...
1
vote
1answer
39 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
0
votes
1answer
32 views

Need help with checking my proof related to equivalence mod n.

Let $n = a_ka_{k-1} \ldots a_1a_0$ be a natural number in base $10$. If $m = a_k + a_{k-1} + \ldots + a_1 + a_0$, then $n\equiv m\pmod n$. $Proof:$ Let $v = 0$, $x =a_k + a_{k-1} + \ldots + a_1$, ...
3
votes
1answer
53 views

Do all primes $p$ except 2 and 3 divide the sum of the squares of integers from 0 to $p - 1$?

I stumbled upon this relationship while working on a completely unrelated problem, and upon testing it for all primes less than 100, it was true. I figure that this is not a coincidence; I just don't ...
1
vote
0answers
25 views

variation of the Euler $\phi$ function?

Let $n \leq m$ be positive integers. Is there a function or expression giving the cardinality of the set $\{r \in \mathbb{Z}^+| 1 \leq r \leq m, \gcd(r,n) = 1 \}$? If $n = m$, it's just $\phi(n)$.
3
votes
0answers
86 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
40 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
38 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
83 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
67 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
127 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
66 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
38 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
200 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
54 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
29 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
45 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
28 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
45 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
39 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
27 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
62 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
51 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$?