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

learn more… | top users | synonyms

0
votes
1answer
11 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
33 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
0answers
19 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$, ...
2
votes
1answer
35 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
24 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)$.
0
votes
0answers
43 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 ...
3
votes
0answers
79 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
39 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
36 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
82 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
66 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
120 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
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
188 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
28 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
44 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
86 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$, ...