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

learn more… | top users | synonyms

1
vote
2answers
18 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
27 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
47 views

is a given expression an irreducible fraction

The following statement is pretty obvious: ...
1
vote
2answers
44 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
19 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
25 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
41 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
19 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
58 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
49 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
24 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
43 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
23 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
79 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
26 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
47 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
16 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$ ...
5
votes
2answers
122 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
27 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
1answer
20 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
34 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
4answers
52 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
5answers
99 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
45 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 ...
1
vote
2answers
79 views

Let $n$ be a positive integer. Let $p$ be a prime divisor of $n^{2}+3$. Prove that $p\equiv 1\pmod 3$

Let $n$ be a positive integer. Let $p$ be a prime divisor of $n^{2}+3$. Prove that $p\equiv 1\pmod 3$ Hint: $\left(\frac{n^2}{p}\right)=\left(\frac{-3}{p}\right)$ I know that this implies that ...
0
votes
2answers
35 views

Number theory proof regarding congruences and common divisors

Anyone know how to prove the following statement? If $ a=b $ (mod m) then the common divisors of a,m are the same as those of b,m
0
votes
0answers
17 views

Given an integer n find smallest integer i such that σ(i)=n. Smallest Inverse Sum of Divisors

Hi All I need some help I am trying to solve this problem which involves computation of sum of divisors and its inverse. In other words Given an integer n find smallest integer i such that σ(i)=n ...
-2
votes
1answer
43 views

Suppose $x ≡ 1 \ (\text{mod}\ 8)$, and $x ≡ 9\ (\text{mod}\ 12)$ has a solution $x = x_0$. How many solutions modulo 24? [on hold]

Suppose $x ≡ 1\ (\text{mod}\ 8)$, and $x ≡ 9\ (\text{mod}\ 12)$ has a solution $x = x_0$. How many solutions modulo $24$ are there to this system of congruences?
-3
votes
0answers
27 views

For m, n ≥ 2, let f : Z → Z/mZ×Z/nZ be the ring homomorphism defined by f(a) = (a + mZ, a + nZ)… read below. [on hold]

For m, n ≥ 2, let f : Z → Z/mZ×Z/nZ be the ring homomorphism defined by f(a) = (a + mZ, a + nZ). (i) The kernel K of f is the ideal qZ for some number q (depending, of course, on m and n). Describe q. ...
2
votes
1answer
40 views

Problem regarding Euler's Theorem: $a^{\phi(n)}\equiv 1 \bmod n$

Here's the problem: If $n \geq 2$, and if $p$ is a prime number s.t $p|n$ but $p^2$ is not a factor of $n$, then $$p^{\phi(n)+1}\equiv p \mod n$$ So since we're dealing with Euler's Phi ...
0
votes
1answer
36 views

Number theory proof regarding norms

How would you prove that if $x$ is a prime in $ℤ[i] \Longleftrightarrow$ $N(x)$ is a prime in $ℤ$ N(x) represents the norm of x.
-2
votes
3answers
140 views

Equation $a^{n}+b^{n}=2008$ has no integers solutions. [on hold]

Prove that the equation $a^{n}+b^{n}=2008$ has no solutions for $a,b,n\in\mathbb{Z}, n\geq2.$
0
votes
1answer
33 views

Let $x$ be an integer with $x \ge 5$. Show that $x + y$ is a perfect square where $y > 0$ and $x > y$.

I have asked this question before, but didn't really understand the answer given. I found this proof elsewhere. $Proof:$ $a^2 \le x < (a + 1)^2$ is true for some (unique) positive integer $a$. ...
7
votes
1answer
94 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
2
votes
7answers
106 views

Prove that if the square of a number $m$ is a multiple of 3, then the number $m$ is also a multiple of 3.

I'd like to prove that if ${m}^{2}$ is a multiple of 3, then ${m}$ is also a multiple of 3. Similarly, I'd like to disprove that if ${n}^{2}$ is a multiple of 4, then ${n}$ is also a multiple of 4. ...
0
votes
2answers
42 views

Number theory proofs regarding units and orders

Hey I just came across this proof but I have no idea how to prove this. If $u$ ∈ $U_m$ has order $n$ and ($k,n$) = 1, then $u^k$ has order n. Any ideas?
1
vote
1answer
50 views

Odd Natural number and perfect squares

Find all odd natural numbers $n$ for which there is a unique perfect square strictly between $n^2$ and $2n^2$. I considered some numerical examples $3$ is and odd number and between $3^2$ and ...
0
votes
1answer
35 views

Squares, Cubes and Prime numbers

Suppose $p$ and $p^2+2$ are prime numbers, prove that $p^3+2$ is also a prime number. Actually I do not know what is the relationship among square numbers, cube numbers and prime numbers
0
votes
1answer
40 views

Finding solutions to equations in $Z_{143}$

How would you find all solutions to the equation $x^2=3$ in $Z_{143}$? I don't really know where to start.
0
votes
2answers
125 views

$9n^2-4$ only generates one prime? Why?

Instead of doing the work I was supposed to be doing, I played around with some numbers, and I noticed that for $n\in\mathbb{N}$, $9n^2-4$ only seems to generate a prime for $n=1$. Can anyone ...
0
votes
0answers
21 views

No of unique values [on hold]

How to find the number of uniques values AX+BY can take under various scenarios Like (A,B) being co-prime or GCD(A,B)=C,with the imposed conditions like X,Y being integers from the set (E,F).
0
votes
4answers
109 views

Is at least one of $6k + 1$ or $6k-1$ prime?

We know that any prime number ( $> 2,3$) can be written in the form $6k+1$ or $6k-1$. Is it necessary that at least one of $6k+1$ or $6k-1$ is a prime number ?
2
votes
2answers
31 views

Using modular arithmetic to find$ [2^{16}]_8$…

This is a fairly simple problem. Just wanted to check if there's another method that I should of used. Here goes--- The problem: Find $2^{16} \mod 8$ So I figured this one out pretty quickly, ...
1
vote
0answers
21 views

Elementary Application of Legendre Symbol [duplicate]

For odd primes $p,q$ with $p\equiv q\pmod{4a}$, then how can we show that $a$ is a quadratic residue $\mod p$ if and only if it is a quadratic residue $\mod q$ using legendre/jacobi symbols?
2
votes
1answer
48 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
0
votes
1answer
38 views

If $x$ is an integer and $x \ge 5$, then there's $y$ such that $x + y$ is a perfect square with $x > y$.

$y < 5 \le x$ by hypothesis. Let $y = -x$. Then, $-x + x = 0$. Since $0$ is a perfect square, we are done. I am not sure if this proof would fly. Please, tell me what you think.
1
vote
1answer
51 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
-1
votes
1answer
32 views

Who will be last [on hold]

There are n children in school and teacher is going to give some candies to them. Let's number all the children from 1 to n. The i-th child wants to get at least a[i] candies. Teacher asks children ...