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

learn more… | top users | synonyms (1)

1
vote
1answer
44 views

Complexity of primenumber test

The german wiki claims that the approach to check if any number before p is a divisor of p is a polynomial time algoritm. I dont understand this claim. Because imho this is linear, which is polynomial ...
1
vote
0answers
54 views

A simple equivalence relation problem

For the set of all subsets of R, let $A \sim B$ mean that $A \subseteq B$ ($A$ is a subset of $B$). Question: Is this an equivalence relation? If not explain why. Attempt at solution: Reflexive- If ...
2
votes
1answer
546 views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
1
vote
0answers
194 views

Find the sum of all positive two digit integers that are divisible by each of its digits?

As for this one, I think I could count the number by hand, eliminating the numbers that contain prime numbers. But best if you could use variables!
0
votes
2answers
46 views

How can you compute $a^b \mod n$ in polynomial time to the length of the input $(a,b,n)$?

I know there are efficient methods for modular exponentiation, but I'm having trouble understanding exactly what "polynomial" refers to in this case. What's wrong with just computing $x = a^b$ then ...
3
votes
1answer
154 views

Consecutive quadratic residues

I was studying quadratic reciprocity laws and came across the following question: Is it true that for every $k \in \mathbb{N} $ there exists a prime $p$ such that $1,2,...,k$ are all quadratic ...
2
votes
2answers
75 views

Show that for all integers $a,b$ and every $n>0$, $(a+b)^n ≡ a^n + b^n \pmod 2$

I want to show that, for all integers $a,b$ and every $n>0$, $(a+b)^n ≡ a^n + b^n \pmod 2$. I know that $$(a+b)^n = a^n + \dbinom{n}{1}a^{n-1}b + \cdots + \dbinom{n}{n-1}ab^{n-1} + b^n.$$ I know I ...
3
votes
1answer
63 views

Does every finite cyclic group appear as a subgroup of the multiplicative group of a finite field?

Does every finite cyclic group appear as a subgroup of the multiplicative group of a finite field? In other words, given any $d \in \mathbb{N}$, can we find a prime $p$ and $k \in \mathbb{N}$ such ...
1
vote
1answer
33 views

Show that λ(m)<Φ(m) for every odd composite number m.

I know that every odd composite number m factors into a set of odd primes. m=p1^(e1)p2^(e2)***pn^(en). I believe that in this situation λ(m)=[(p1-1)^(e1), (p2-1)^(e2), . . ., (pn-n)^(en)], but please ...
0
votes
2answers
24 views

Verifying that $11^{λ(m)+1} ≡ 11 \pmod m$ for $m = 41 \cdot 11$

I know that $λ(m) = [40, 10] = 40$ So I need to show that $11^{41} ≡ 11 \mod 451$. From here I believe I should show that $11^{41} ≡ 11 \mod 41$ and that $11^{41} ≡ 11 \mod 11$, but I am not sure how ...
0
votes
1answer
42 views

If a power of a prime number say $p^r$ does not divide $n!$ then $\frac{n}{p^r}<1$

I'm busy with a proof with $p-adic$ numbers and I need to show that if $p^r\nmid n! \implies \frac{n}{p^r} < 1$ where $p$ is prime. I need this to show $\lfloor \frac{n}{p^r} \rfloor = 0$ Any ...
3
votes
1answer
110 views

Finding all possible values

we have to find all possible prime values $(p,q,r)$ such that $ pq = r + 1 $ $ 2(p^2+q^2) = r^2 + 1 $ I do not know how to start looking for an answer.
1
vote
2answers
359 views

Find the next divisor without remainder

I divide a value and if the remainder is not 0 I want the closest possible divisor without remainder. Example: I have: $100 \% 48 = 4$ Now I am looking for the next value which divide 100 wihtout ...
3
votes
2answers
317 views

Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$ [duplicate]

Prove that:$$\sum_{d\mid n} \varphi(d)=n$$ Where $\varphi(n)$ denotes the number of positive integers $m$ less than or equal to $n$ such that $\gcd(m,n)=1$ I am lost here, any help would be ...
6
votes
1answer
70 views

Sum of a certain series related to the primes

It is well known that $$\sum_{n > 0}\frac{1}{n}$$ diverges, but $$\sum_{n > 0}\frac{1}{n^2} = \frac{\pi^2}{6}$$ converges. Similarly, $$\sum_{p}\frac{1}{p}$$ diverges, but $$\sum_{p} ...
1
vote
3answers
88 views

Can we find positive integers $a$ and $k \geq 2$ with $2^n - 1 = a^k$?

I would appreciate if somebody could help me with the following problem: For a given positive integer $n$, can we find positive integers $a$ and $k$ ($k\geq 2$) such that $2^n-1=a^k$? The ...
0
votes
1answer
60 views

Finding Bezout coefficients

$$3 − 1 · (23 − 7 · 3) = −1 · 23 + 8 · 3$$ How does one get the left side to become the right side? Is it algebra? My discrete math textbook just wrote this but never explained a step by step process ...
1
vote
2answers
45 views

A special example of extended Euclidean algorithm

Find natural number $x$ so that $$x\equiv 9\pmod{10},\quad x\equiv8\pmod9,\quad ...,\quad x\equiv 1\pmod2$$
0
votes
1answer
14 views

How to conclude the congruence $2\cdot \text{disc}(F)\equiv 2b^2c^2\in\mathbb{Z}$

I am studying a proof which shows that the cubic form $F(x,y)=ax^3+bx^2y+cxy^2+dy^3$ is integral (i.e has integer coefficients.) So far I have the following facts: $a,d\in\mathbb{Z}$, ...
6
votes
1answer
73 views

Is there any advantage to the $a \equiv b\;\;(\mathrm{mod}\;c)$ notation?

Congruences modulo equivalence classes other than those defined by division remainders are ubiquitous in contemporary mathematics. It is not uncommon for a single mathematical argument to refer to ...
0
votes
1answer
35 views

Proving that $mx \equiv 0 \pmod n$ has $\gcd(m, n)$ solutions in the interval $[0, n-1]$

I wish to prove, using my own intuition, that there are $\gcd(m, n)$ group homomorphisms from $\mathbb{Z}_m$ to $\mathbb{Z}_n$. I have reduced(?!) the problem to proving that there are $\gcd(m, n)$ ...
0
votes
1answer
45 views

$p$ is an odd prime of the form $p=x^2+2y^2$ iff $p\equiv_8$ $1$ or $3$ [duplicate]

How would I prove the following: Show that an odd prime $p$ can be written on the form $p=x^2+2y^2$ for some $x,y\in\mathbb Z$ iff $p\equiv_8 1, 3$. Hint: use the quadratic reciprocity and the ...
2
votes
2answers
80 views

On last digit of 4 consecutive primes less than 10 apart

$\def\mod{\mathrm{\;mod\;}}\def\pq{\{p_1,p_2,p_3,p_4\}}$$\def\dq{\{d_1,d_2,d_3,d_4\}}$ This question concerns quartets of consecutive primes $p_1 < p_2 < p_3 < p_4$ such that $p_4 - p_1 < ...
0
votes
1answer
76 views

The number of numbers not divisible by $2,3,5,7$ or $11$ between multiples of $2310$

Looking at partitions of the natural number line of the form $P=[a,b)$, I noted that if $a$ and $b$ are multiples of $6$, there exist at least $2$ numbers in the partition which are not divisible ...
1
vote
6answers
267 views

Solution of $\dfrac{a}{b}=\dfrac{a'}{b'}$ if $a,b,a',b' \in \mathbb{N}$

Let $\dfrac{a}{b}=\dfrac{a'}{b'}$ , $a,b,a',b' \in \mathbb{N}$ s.t. $a$ and $b$ have no common factors. How can we show that the only solution to this equality is $a'=na$ and $b'=nb$, $n$ is a natural ...
1
vote
3answers
264 views

Prove that no number in this list is prime - Formatting a proof advice

Question: Let $n \in \mathbb{Z}$ where $n \geq 2$, prove no number in the list: $$n! + 2, n! + 3,...,n! + n$$ is prime. I have written my proof exactly as follows: Proof: $P(n) = n! + n = ...
5
votes
1answer
202 views

On proving $n = \sum_{d\mid n}\varphi(d)$

$\def\nset{\{1,\dots,n\}}$ I'm trying to work out my own proof1 of Euler's classic formula $$n = \sum_{d\mid n}\varphi(d)\;.$$ I'm looking for some pointers to the standard terminology and/or ...
2
votes
1answer
126 views

show that the number is not prime

$x,y>2$ and $\in\mathbb{N}$. Show,that if $x^2+y^2-1$ is divided by $x+y-1$, then $x+y-1$ isn't prime. $$x^2+y^2-1=(x+y)^2-1-2xy=(x+y-1)(x+y+1)-2xy$$ Thefore, $2xy=k(x+y-1), k\in\mathbb{N}$. Some ...
1
vote
1answer
106 views

Is this a correct definition of the natural numbers in ZF?

Set $s$ is a natural number if $s$ is transitive and for every $x$, $y$ and $z$ $y\in{s}\rightarrow(y$ is transitive$)$, and if $x\in{P}s\wedge(x$ is transitive$)\wedge{z}\in{P}x\wedge(z$ is ...
13
votes
4answers
784 views

Prove that e is irrational

Prove that e is an irrational number. Recall that e $=\displaystyle\sum_{n=0}^\infty\frac{1}{n!},\,\,$ and assume $\mathrm{e}$ is rational. Then $$\sum\limits_{k=0}^\infty \frac{1}{k!} = ...
0
votes
1answer
100 views

Prove that $2^x \cdot 3^y - 5^z \cdot 7^w = 1$ has no solutions

Prove that $2^x \cdot 3^y - 5^z \cdot 7^w = 1$ has no solutions in $\mathbb{Z}^+$, if $y\ge 3$.
3
votes
2answers
91 views

Observations needed to justify an algebraic passage in proof of a property of $\varphi$ (Totient function)

Let $\varphi$ be the Euler's totient function and let $n\in \mathbb{N}$ be factorized in primes as $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_l^{\alpha_l}$. I was looking for alternative methods to ...
1
vote
1answer
78 views

On $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$ [duplicate]

How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $ n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)
2
votes
2answers
181 views

Reciprocity problem in I&R “A Classical Introduction in Modern Number Theory”

Let $\pi = a+bi \in \mathbb{Z}[i]$ and $q \equiv 3 \pmod{4}$ a rational prime. Show that $\pi^q \equiv \bar{\pi} \pmod{q}.$ It's a problem from chapter 9 "cubic and biquadratic reciprocity" of ...
0
votes
2answers
81 views

Is there a formula for a simple sum of sums?

Given $f(n) = 1 + (1 + 2) + (1 + 2 + 3)+ \cdots + (1 + 2 + 3 +\cdots + n)$, I am wondering if there is a straightforward formula to compute f(n) and how it may be ...
8
votes
0answers
235 views

A question on odd perfect numbers

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(M) = 2M$, then $M$ is said to be perfect. Currently, there are $48$ known examples of even perfect numbers -- on ...
4
votes
1answer
109 views

How to solve $79 n + 1 = 2^a 3^b$

How could you solve something like: Find the smallest $n \in \mathbb N^+$ such that $79 n + 1 = 2^a 3^b$ for some $a,b \in \mathbb N$ by non-brute force methods?
0
votes
1answer
65 views

If m divides n, prove that a^m-b^m divides a^n-b^n.

To make a long story short, I have a two part homework in an elementary number theory course I'm currently doing at uni. First part is to prove that $(a-b)$ divides $(a^n-b^n)$ with $a,b ...
2
votes
1answer
43 views

Existence of primes Of a given form

Given a prime $p$ and an integer $n \neq 1$, not divisible by $p$, does there always exists a prime, or possibly infinitude of primes $q$ such that $p+nq$ is also prime? Same questions when $P$ is ...
26
votes
4answers
3k views

Any natural number is greater than or equal to its product of digits.

I was randomly thinking and I stumbled upon this question in my mind. I was thinking of numbers, and I observed that any number is greater than or equal to the product of digits in many cases. I was ...
3
votes
2answers
185 views

Are even numbers the sum of two odd sub-primes? / How to use computers to check?

Suppose $$p_{a} + p_{b} = 2{p_{1}}^{m_{1}}{p_{2}}^{m_{2}}...{p_{n}}^{m_{n}} \qquad \text{where }p_{x} \in \mathbb{P} -\left\{2\right\} $$ Then $$\frac{p_{a} + ...
6
votes
1answer
500 views

Count expressions with 1s and 2s

Given at most X number of 1s and at most Y number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * ...
1
vote
3answers
1k views

Divisibility by $8$ for permutations of numbers

Moderator's note: This is an on-going contest problem. Per usual protocol the answers have been hidden and the question is locked until after the contest ends. (21.03.2014) Given an integer $N$. ...
3
votes
1answer
41 views

$a^4 = x^2 + y^2 (6+8b)$ solutions $(x,y)$?

Given constants $a,b \in \mathbb{Z}$, can we find $(x,y)$ such that $a^4 = x^2 + y^2 16(6+8b)$ has a solution? Alternatively: consider the ring $\mathbb{Z}[4\sqrt{-m}]$ with $m \equiv 6 ...
1
vote
1answer
163 views

The Cantor Set and Triadic Expansion

let $K$ be the Cantor set. I say that a number $x$ in $[0,1]$ is triadic if $x=\frac{m}{3^n}$ for some nonnegative integers $m, n$. Let $z$ be a triadic number in $[0,1]$. Do there exist two ...
0
votes
0answers
63 views

Show that the number of elements in the equivalence class is n?

Question is : Let $G$ be a finiote group of order n = $p^{\alpha}$m, where $p$ is a prime number and if $p^r$ | m but $p^{r+1} \nmid$ m Let $\mathcal M$ be the set of all subset of $G$ which have ...
3
votes
2answers
117 views

Prime factorization of $10^n+1$

I was just playing with these numbers and it seems to me that the numbers of the form $10^n+1$, where $n>2$ are composite. I can prove that $10^n+1$ can't be prime unless $n$ is a power of $2$, but ...
0
votes
3answers
214 views

Finding values for Chinese Remainder Theorem

So I have looked over a lot of the other Chinese Remainder Theorems on here and I still can not completely understand how to answer my question. The question is "Use the construction in the proof of ...
0
votes
1answer
101 views

Proving Legendre's Formula

Where $v_p(n)$ is called the $p$-adic valuation of $n$. prove $v_p(n!)=\sum_{t=1}^\infty \left\lfloor \frac{n}{p^t} \right\rfloor$ so far i have that $v_p(n!) = v_p(n) + v_p(n-1) + \cdots + v_p(2) + ...
1
vote
1answer
102 views

Another unproven conjecture is that there are an infinitude of primes that are 1 less than a power of 2

Another unproven conjecture is that there are an infinitude of primes that are 1 less than a power of 2. If p=2^k-1 is prime, show that k is an odd integer, except when k=2 Hint: 3|4^n-1 for all n>=1 ...