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

learn more… | top users | synonyms

0
votes
0answers
10 views

Can irreducible non linear polynomial over $\mathbb{Z}$ have bounded factorization going to infinity?

i've the following question. Suppose that a $f(x) \in \mathbb{Z}[x]$, is such that you have a strictly increasing sequence $\{x_n\}$ of natural numbers such that the primes dividing $f(x_n)$ are all ...
3
votes
2answers
21 views

Math for Computer Science

I have a couple of questions on the material in "Mathematics for Computer Science" by Eric Lehman and Tom Leighton. Q1. This is a theorem in the book: Theorem 24. Let $p$ be a prime. If $p|a_1a_2 ...
0
votes
0answers
8 views

Can this matrix be said to consist of Dirichlet characters?

When: $j=1$ the following formula: $$T(n,k)=\prod\limits_{m=1}_{m \mid n}^{\text{n}} \left(\exp ^{-\mu \left(\frac{n}{m}\right)}\left(\Lambda \left(\frac{n}{m}\right)\right) \chi _{\exp ^{-\mu ...
2
votes
2answers
32 views

If $d$ is a natural number and $d^2$ divides $y^2$ then does $d$ divide $y$?

If $d$ and $y$ are positive integers and I know that $d^{2}|2y^{2}$ then $d^2|2$ (i.e $d=1$) or $d^2|y^2$ . In the case that $d^2|y^2$ does that imply that $d|y$ for all $d,y$ ? Thank you.
-4
votes
0answers
34 views

Revisiting 0.99999… and more [on hold]

Do you agree or not? Those who look for duplicate posts to this one might find this on the post that asks: “I'm told by smart people that 0.999999999...=1 and I believe them, but is there a proof ...
1
vote
3answers
69 views

If $x^2$ is divisible by $4$ then $x$ is even?

I am studying discrete mathematics as course and I have to prove this "If $x^2$ is divisible by $4$ then $x$ is even". I am wondering how to prove it using the contrapositive of this ...
0
votes
2answers
16 views

finding the largest term in a binary summation

I'm working on a problem that involves the following summation: $$y=\sum_{i=0}^{x}i2^i$$ I need to determine the largest value of $x$ such that $y$ is less than or equal to some integer K. Currently ...
0
votes
1answer
13 views

Rings with zero-divisors

this might be an odd question but I know that in a ring with no zero-divisors $ac|bc$ implies $a|b$, if $c\neq 0$. So are there Rings with zero divisors where $ac|bc$ still implies $a|b$? Thank you.
2
votes
0answers
46 views

Conjecture on sum of powers

Let $n$ be an odd number, $x,y$ integers and $p$ a prime number. Now, suppose that $p\ne n$ and $$ p|\frac{x^n+y^n}{x+y} $$ Then, I have been observed that $p \equiv 1 \pmod{n}$. This is, all of the ...
0
votes
1answer
18 views

Would someone please explain this argument? (Legendre formula)

Here is an argument in my book. Theorem If $n$ is a positive integer and $p$ is a prime, then the exponent of the highest power of p that divides $n!$ is $\sum_{k=1}^\infty [\frac{n}{p^k}]$ ...
1
vote
2answers
49 views

Prime numbers and $\sqrt{10301}$

On my exam recently, we had the following question: Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime ...
1
vote
1answer
22 views

Proofs of the following gcd Theorems.

Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$. Theorem 2: Let $a$ and $b$ be nonzero integers. The ...
1
vote
1answer
56 views

Triplets of distinct integers > 1 that return integer values.

If $(A, B, C)$ are distinct integers $> 1$, and $$f(A, B, C) = \frac{\frac{A^2-1}{A} + \frac{B^2-1}{B}}{\frac{C^2-1}{C}},$$ then for what (if any) triplets $(A, B, C)$ is $f(A, B, C)$ an integer? ...
0
votes
0answers
15 views

Why is $k^n \equiv 0 (mod k^2)$ in this case?

It is written in my text that: Let $n$ be an absolute Fermat pseudoprime. Claim : $n$ is square free Suppose there exists $k>1$ such that $k^2$ divides $n$. Since $n$ is an absolute ...
2
votes
3answers
48 views

How to prove that $\gcd(2n+3, 3n+1)$ divides $7$?

How can I start proving that gcd(2n+3, 3n+1) | 7? EDIT: It is $\gcd(2n+3, 3n+1)$ divides $7$. My bad. Thanks paw88789.
1
vote
0answers
27 views

Generalization of Hensel's lemma

I've been trying to prove the following generalization of Hensel's lemma: Let $ f\in \mathbb{Z}[x_1, \dots, x_n] $ and $ f=0 $ be a diophantine equation. Let's assume that for some $ d \in ...
0
votes
1answer
32 views

Find out $f(n)$ where n is an integer

Suppose I need a function $f(n)$ such that $f(n)$ is odd when $n=4,12,20,28...$ and even when $n=8,16,24,32...$. Then the answer would be $f(n)=\frac{n}{4}$. Similarly, now suppose I need $f(n)$ such ...
12
votes
2answers
155 views

Integer solutions of $x^3-x+9=5y^2$

What are the solutions in integers of $x^3-x+9=5y^2$? [Source: Hungarian competition problem]
1
vote
1answer
23 views

About primitive roots.

Assuming 6 is a primitive root mod p ( for some odd prime p) ( assuming this is possible) then could p have another distinct primitive root n (such that 1 < n < (p-1)) where 2 | n? ( n not equal ...
1
vote
2answers
57 views

How to find all cyclic quadrilaterals with integer sides?

We need to find all cyclic quadrilaterals (or formulas that gives its sides), which have integer sides $a,b,c,d$. The constrain is that its area must be an integer multiple of its perimeter. We can ...
0
votes
1answer
30 views

If $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$, then $ab \pmod 3 \equiv 2$

I'm stuck on this this problem: Let $a$ and $b$ be positive integers with $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$. Prove that $ab \pmod 3 \equiv 2$. I think the first step for the direct ...
2
votes
1answer
30 views

Definition of field of fractions of $p$-adic integers

I am given this definition of the field of fractions of the p-adic integers: $$Q_p=\left\{ \frac{r}{s} \mid r, s \in Z_p, s \neq 0\right\}$$ How can I show that: $Q_p$ consists of the sums of the ...
0
votes
0answers
19 views

Calculate sum of distinct pairs [closed]

Given an array A we need to find the sum of all distinct pairs of indexes from the array and adds the value ⌊$A[i]+A[j]\over A[i]×A[j]$⌋ to the sum Note: ⌊$A\over B$⌋ is the integer division ...
1
vote
2answers
32 views

figure out $f(n)$ under given conditions

Suppose I need a function $f(n)$ such that $f(n)$ is odd when $n=4,12,20,28...$ and even when $n=8,16,24,32...$. Then the answer would be $f(n)=\frac{n}{4}$. Similarly, now suppose I need $f(n)$ such ...
2
votes
0answers
24 views

find other sums similarly under sum

In the under sum there exists all number 1,...,9. Similarly write at least 10 sums other. $$659+214=873.$$ For example we can write $259+614=873$ or $619+254=873$ or $596+142=738$. Do there exists a ...
2
votes
4answers
48 views

How to find the $n$th term of a repeating pattern

What is the nth term of following sequence $1,2,3,4,5,6,1,2,3,4,5,6,\ldots$ $(n, n+1, n+2, n+3,\ldots,$ $,n+p, n, n+1, n+2, n+3,$ $n+4, n+5,$ $\ldots,$ $n+p,$ $n,$ $n+1,$ $\ldots)$ Actually, I am ...
3
votes
4answers
101 views

Prove that $2^{10}+5^{12}$ is composite

Prove that $2^{10}+5^{12}$ is composite I need to solve this using only high school mathematics. Any ideas?
8
votes
5answers
149 views

$2^{50} < 3^{32}$ using elementary number theory

How would you prove; without big calculations that involve calculator, program or log table; or calculus that $2^{50} < 3^{32}$ using elementary number theory only? If it helps you: $2^{50} ...
0
votes
4answers
44 views

Proving $\gcd(a,b) = ax+by \Rightarrow \gcd(x,y) = 1$

I'm not entirely sure of how I should prove this statement: $$ \gcd(a,b) = ax+by \Rightarrow \gcd(x,y) = 1 $$ So I've tried $$ \begin{align} &\gcd(x,y) = d \Rightarrow x =x'd, y=y'd\\ ...
2
votes
1answer
38 views

Number of integers of the form $3k+1$ in range $[a,b]$ [on hold]

How do I find the number of integers in the range $[a, b]$ that are of the form $3k+1$, where: $a,b,k$ are natural numbers. $a \le b$
2
votes
3answers
58 views

$\dfrac1a+\dfrac1b=\dfrac1c$, $a, b, c \in \mathbb{N}$ with no common factor, find all solutions [duplicate]

Given $\dfrac1a+\dfrac1b=\dfrac1c$, where $a, b, c \in \mathbb{N}$ with no common factor, find all solutions. Actually, you can think this question as a follow up of this one. Today, I saw this ...
1
vote
1answer
41 views

problem about Euler function $\phi$.

For a positive $m$, let $\phi(m)$ denotes the number of integers $k$ such that $1\leq k\leq m$ and $GCD(k,m)=1.$ Then which are necessarily true? (1) $\phi(n)$ divides $n$ for all $n>0$ (2) $n$ ...
0
votes
0answers
22 views

Existence of an integer satisfying this equation

I want to know whether there exists an integer N, for which: {(b+N.d) mod (a-N.c)} = 0 a, b, c, d are integer constants and, (a-N.c)>1 , a >= b , c < d I ...
0
votes
2answers
35 views

How to design a function $f$ such that $f(x) \not\equiv f(y)\,(\text{mod } n)$? [closed]

$x$, $y$, and $n$ are known, $x \neq y$, and $x\equiv y\,(\text{mod } n)$. I try to design a function $f$ that $f(x) \not\equiv f(y)\,(\text{mod } n)$. Thanks
0
votes
2answers
25 views

Is it true that $\sum\limits_{n=1}^N e^{in} = \frac{e^i(1-e^{iN})}{1-e^i}$ even if $| e^i | > 1$?

Is it true that $\sum\limits_{n=1}^N e^{in} = \frac{e^i(1-e^{iN})}{1-e^i}$ even if $| e^i | > 1$? I know this question is quite trivial and I will understand if it gets removed. I am trying to ...
0
votes
1answer
14 views

Solving a congruence — where to start?

For which positive integers $n$ is it true that $$1^2 + 2^2 + \cdots + (n − 1)^2 \equiv 0 \,(\text{mod } n)$$ I have no idea where to start. I'm just looking for a nudge in the right direction. Any ...
-1
votes
2answers
73 views

Why multiplication should be a secondary binary operation?

Isn't every multiplication resumed in a simpler summing operation? For instance: $5 \times 2 = 5 + 5$; or $5 \times 1/2 = 1/2 + 1/2 + 1/2 + 1/2 + 1/2$; or $1/2 \times 1/2 = 1 \times 1/4 = 1/4$. Why ...
0
votes
1answer
33 views

Is $\sum\limits_{\text{p prime}, p \geq 2}\frac{(-1)^{\frac{p^2-1}{8}}}{p}$ convergent or divergent??

Is $\sum\limits_{\text{p prime}, p \geq 2}\frac{(-1)^{\frac{p^2-1}{8}}}{p}$ convergent or divergent? So far I have that \begin{align} \sum\limits_{\text{p prime}, p \geq 2} ...
2
votes
1answer
34 views

The congruence has a solution

Sentence: If $a \in \mathbb{Z}$, then the congruence $x^2=a \pmod p, \forall p \in P$ has a solution $\Leftrightarrow$ $a=\square$ in $\mathbb{Z}$. If $a=\square$, then $\exists d \in \mathbb{Z}$ ...
4
votes
2answers
46 views

$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$ please do not use fancier stuff like the prime number theorem or beyond. using this how can you show that ...
0
votes
0answers
26 views

The sets are equal

I want to show that $Z_p^*= \{ x \in Z_p | |x|_p=1 \}$. I have tried the following: Let $x \in Z_p^*$, then $x=a_0+a_1p+a_2p^2+ \dots \ \ \ \ \ \ \ \ 1 \leq a_i \leq p-1$. So, $x \in Z_p $. When ...
0
votes
0answers
4 views

Most negative number in the von Mangoldt function minus $n$, what describes this sequence?

I am looking into what the most negative number is in the von Mangoldt function minus $n$. Consider the matrix $T$ defined by: $$T(n,k)=a(GCD(n,k))$$ where: $$a(n) = \lim\limits_{s \rightarrow 1} ...
0
votes
0answers
28 views

Identity of the $p-$norm

A $p-$ norm of $\mathbb{Q}_p$ is a function $||_p: \mathbb{Q}_p \to \mathbb{R}$ $$x \neq 0, x=p^{w_p(x)}u \mapsto p^{-w_p(x)}$$ $$\text{ For } x=0 \Leftrightarrow w_p(x)=\infty \\ p^{-\infty}:=0$$ ...
0
votes
1answer
19 views

Divisibility Test Question of Curisosity

Why do we only do divisibility tests up to 11? At least, in my proofs class and in my textbook, that's all it goes up to: 11. Can anyone explain?
1
vote
2answers
25 views

Elementary Number Theory: Divisibility proof

Let $k,m,n \in N\setminus \{0\}$, s.t. $n=k\cdot m$. Show that $k$ is odd $\Rightarrow ∀ a,b \in Z: (a^m+b^m) \mid (a^n+b^n)$ In the first part of the task, I have already shown that $∀ a,b \in Z: ...
2
votes
2answers
58 views

The Mersenne number $2^{83}-1$ is not prime

There is a solved example on my textbook (in Portuguese) showing that the Mersenne number $2^{83}-1$ is not prime.He says: We have $2^{8}=256\equiv 89\mod 167$ $2^{16}\equiv 72 \mod 167$ ...
6
votes
1answer
545 views

If $m^n = n^m$, why does $m$ to be a factor of $n$?

Let $m^n = n^m$ with $n,m \in \mathbb{N}$ and $n > m.$ Why does $m$ have to be a factor of $n$? I think it's because of the prime factorization, but I can't prove it.
8
votes
2answers
96 views
+50

Triplets satisfying $(a^3+b)(b^3+a)=2^c$

Find the number of triplets $(a,b,c)$ satisfying $(a^3+b)(b^3+a)=2^c$, where $a,b,c\in \mathbb{N}$ A trivial solution is $(1,1,2)$. I think there aren't any other such triplets, so I've been ...
0
votes
0answers
25 views

The representations of numbers by decimals

I'm looking for books that talk about the representation of the integers by decimals, more specifically for prime numbers. I can't found anything yet, I read something in "AN INTRODUCTION TO THE ...
2
votes
2answers
51 views

Show that $\gcd(3n,3n+ 2) = 1$ when $n$ is odd

I would like to know why $\gcd(3n,3n+ 2) = 1$ when $n$ is odd. I tried to use the Euclidean Algorithm, but I got confused: $$ 3n+2 = 3n + 2$$ $$3n = \ ? $$ Thanks!