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

learn more… | top users | synonyms

2
votes
2answers
163 views

Weak Lower Bound in Apostol's “Number Theory”?

In Apostol's "Introduction to Analytic Number Theory" on page 7 he introduces Fermat numbers of the form $F_n = 2^{2^{n}} + 1$ where $n$ is a non-negative integer. He then states that The ...
0
votes
1answer
83 views

Prove if $c\geq ab$, $a|c$ and $b|c$ then $ab|c$

Prove: If $c \ge ab$ and $a|c$ and $b|c$ then $ab|c$. If $a|c$ and $b|c$ then there are integers $p$ and $q$ such that $ap=c$ and $bq=c$ All of my work has boiled down to substitutions, a lot ...
2
votes
1answer
94 views

Divisibility, many unknowns

As I was solving a math problem, I stumbled upon a question: What conditions must $a,b,c,d,e$ meet for $n$ to be a natural number? (Frankly speaking, I would like all but one of $a,b,c,d,e$ to be ...
2
votes
0answers
410 views

Show that $\gcd(2^m-1, 2^n-1) = 2^ {\gcd(m,n)} -1$ [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ $\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ I'm trying to figure this out: ...
4
votes
2answers
390 views

Coprime numbers

Why is it true that if $a, b$ are coprime then there exists an $N$ such that for all $n> N,$ $n$ can be expressed as $n= ca+db$ where $c, d$ are non-negative? Thanks.
4
votes
2answers
505 views

Finding the maximum number with a certain Euler's totient value

Euler's totient function has a lower bound for large values, but is there any way to pick out maximums for specific values of the function? That is, how would I find the maximum number n such that ...
9
votes
3answers
1k views

Find all odd primes $p$ for which $15$ is a quadratic residue modulo $p$

I want to find all odd primes $p$ for which $15$ is a quadratic residue modulo $p$. My thoughts so far: I want to find $p$ such that $ \left( \frac{15}{p} \right) = 1$. By multiplicativity of the ...
5
votes
2answers
136 views

Tricky congruence question

Let $p>5$ be a prime, $$n\triangleq\frac{4^p+1}{5}\;\quad\text{and}\;\quad b\triangleq\frac{n-1}{4}\quad.$$ It can be shown that both are integers, and also that $n$ is composite, $b$ is odd and ...
4
votes
1answer
195 views

How to find the prime divisors of repunit $R_{13}$ and $R_{79}$?

The question is very simple: Find a prime divisor of $\frac{(10^{13}-1)}{9}$ , i.e. $11\cdots11$($13$ ones), also known as $R^{(10)}_{13}$ or $R_{13}$. Same question for $R_{79}$. Of course, ...
1
vote
1answer
88 views

Can one show that if $\gcd(p^k,b)=1$, then $p^k \nmid b$?

If $\gcd(a,b)=1$ and $p \mid a$ then $p \nmid b$. But how one can show that $\gcd(p^k,b)=1$? And can one show that if $p^k \nmid b$, then $\gcd(p^k, b)=1$? And can one show that if $\gcd(p^k,b)=1$, ...
1
vote
1answer
98 views

Given $a$ and $n$, find $y \equiv \frac{n!}{a^x} \bmod a$

Take $n!$ and find $x$, where $a^x$ is the greatest power of $a$ who divides $n!$ Then find $y$, where $y \equiv \frac{n!}{a^x} \bmod a$ For example, if $a=3$ and $n=6$ then ...
1
vote
1answer
87 views

How is following possible: $\gcd(a_{n-1}, a_n) \mid a_{n-1}$ and $\gcd(a_{n-1}, a_n) \mid a_n$?

Following is extract from the proof that proves following: Let $a_1,\dots, a_n$, such that $a_{i_0} \neq 0$. Show that $\gcd(a_1,\dots, a_n)=\gcd(a_1,\dots, a_{n-2},\gcd(a_{n-1},a_n))$(hint! Show that ...
20
votes
2answers
914 views

What is the millionth decimal digit of the (10^10^10^10)th prime?

What is the millionth decimal digit of the $10^{10^{10^{10}}}$th prime? (This prime is, of course, far larger than the largest currently "known" prime, the latter having nearly 13 million ...
2
votes
5answers
152 views

Why does $a^b \bmod c=(a \bmod c)^b \bmod c$

This may be a very basic number theory question, but I don't understand: Why does $$a^b \bmod c = (a \bmod c)^b \bmod c$$
0
votes
1answer
130 views

Is there a closed form to $a^b \bmod b$ if $b$ is not a prime?

We know $$a^p \equiv a \pmod p\quad p\text{ a prime, }0\leq a \leq p-1.$$ But if we have $b$, not prime, what's the new formula? $$a^b \equiv\ ? \pmod b,\quad b\text{ not a prime, } 0\leq a \leq ...
1
vote
1answer
134 views

Let $y_{1},…,y_{k}$ be in $\mathbb{Z}$. Show that $\exists y \in \mathbb{Z}$ so that $y\equiv y_{1} \pmod {m_1},\dots,y \equiv y_{k} \pmod {m_k}$

Let $k\ge 2 $ and $m_{1},\ldots,m_{k}$ in $\mathbb{N}$ with $\gcd(m_{i},m_{j})= 1 \ (i \ne j)$. We show that $f(x) = x,\ldots,x)$ ist a ring isomorphism $f: \mathbb{Z}/ m\mathbb{Z} \rightarrow ...
0
votes
1answer
86 views

Interscholastic Mathematic League Senior B Division #1

Let n be a positive integer less than 1000. If n^3 has 10 factors, compute the largest value of n.
2
votes
1answer
2k views

Discrete Math - Bézout Coefficients

I'm taking a discrete math course, and were on Bézout Coefficients right now. I kind of understand the algorithm, the generalization. However the example in the book is throwing me off. The steps in ...
0
votes
2answers
95 views

If $a > b > 0$ and $c=a+b$, then $c \bmod a = b$

I have met the following theorem from the book Introduction to Algorithms (3rd ed.) in the number theory section. The theorem states that Prove that if $a>b>0$ and $c=a+b$, then $c \bmod ...
0
votes
1answer
64 views

Does $B_1+z_1 M_1 \equiv B_2 \pmod {M_2}$ mean that $z_1 = (B_2 \bmod M_2 - B_1)/M_1$?

So a mathematician gives me a system like this: $$ \begin{eqnarray*} B_1 + z_1 M_1 &\equiv& B_2 \pmod {M_2} \\ B_1 + z_1 M_1 + z_2 M_1M_2 &\equiv& B_3 \pmod {M_3} \\ ...
1
vote
3answers
720 views

If $x^2+y^2=z^2$, why can't $x$ and $y$ both be odd?

What does the following mean: If $x^2 + y^2 = z^2$ some integers $z$, then $x$ and $y$ can't be both odd (otherwise, the sum of their squares would be $2$ modulo $4$, which can't be a square). So, ...
17
votes
4answers
3k views

How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...
3
votes
2answers
1k views

Show that the number of steps in the Euclidean algorithm is less than $\frac{2\log b}{\log 2}$

Could anyone tell me how to prove this statement? The number of steps in the Euclidean algorithm is less than $\frac{2\log b}{\log 2}$, where $b$ is the larger of the two numbers whose GCD is being ...
1
vote
2answers
85 views

How to show that xyz is even( 2|xyz), when $x+y=z$?

How to show that xyz is even( 2|xyz), when $x+y=z$? for example if x=5, y=12 then z=17. And $2\mid 5 \cdot 12 \cdot 17 $ <=> $2\mid 5 \cdot 2 \cdot 6 \cdot 17 $ ok. One way to show that zyz is ...
0
votes
1answer
679 views

Problem with RSA encryption

Recently I was looking at the RSA encryption scheme and decided to do some examples but this seemingly simple one is bugging me a lot. I chose $p=13$, $q=17$. Let $e=131$, be the encryption key. So, ...
2
votes
2answers
172 views

Show that every large integer has a large prime-power factor

Show that every large integer has a large prime-power factor That is, if $P(n)$ designates the largest number $p^a$ which divides $n$, then $\lim_{n\to\infty}P(n)=\infty.$
3
votes
1answer
110 views

Show that the following identity is formally correct

$$\sum_{k=0}^{\infty}\frac{1}{2^{2k}}\sum_{k=0}^{\infty}\frac{1}{3^{2k}}\sum_{k=0}^{\infty}\frac{1}{5^{2k}}\cdots=\sum_{n=1}^{\infty}\frac{1}{n^2}$$ Ignoring problems connected with convergence and ...
0
votes
1answer
110 views

Prove: if $n$ is a positive integer, then $n^2$ is divisible by 3 with remainder either $0$ or $1$ [duplicate]

Possible Duplicate: Would like a proofreading of my proof Prove that if $n$ is positive integer, then $n^2$ is divisible by $3$ with remainder either $0$ or $1$.
6
votes
5answers
977 views

Inherently discrete concepts

Are there any concepts which are naturally defined only for the integers and so far has resisted any attempts at extension to other fields such as rationals or reals? Does not meet criteria: ...
1
vote
3answers
449 views

Why is 2 totative of 36?

Based on my understanding, the totient of any number K is the number of relative primes to K, i.e. numbers less than or equal to K that do not share a divisor. Everywhere I look is telling me that 2 ...
4
votes
2answers
681 views

Deepest theorems with simplest proofs [closed]

Which are the deepest theorems with the most elementary proofs? I give two examples: i) Proof_of_the_Euler_product_formula_for_the_Riemann_zeta_function ii) Proof that the halting problem is ...
4
votes
3answers
304 views

What is the lowest positive integer multiple of $7$ that is also a power of $2$ (if one exists)?

What is the lowest positive multiple of $7$ that is also a power of $2$ (if one exists)? Not a homework question, I am not in school, I am just wondering what the answer is.
1
vote
2answers
99 views

Is there a prime $p$ such that $4$ has odd order modulo every power of $p$?

Does there exist a prime $p \geq 7$ such that the order of $4$ in the multiplicative group of units in $\mathbb{Z}/p^n$ is odd for every positive integer $n$? It would be nice if $7$ was already an ...
4
votes
2answers
287 views

Prime counting function inequality

It seems to be the case that for any integer $x > 1 $, we have $ x \leq 2^{\pi(x)} $ I'm not sure whether this is obviously true, annoyingly false or difficult to prove. I'm hoping it's the ...
8
votes
1answer
117 views

Existence of sequence such that $N$ divides the sum of the first $N$ terms for all $N$

Does there exist a sequence $a_n$ which consists of every natural number and for each $N$, $\sum\limits_{k=1}^N a_k$ is divisible by $N$?
2
votes
1answer
84 views

Possible values of $\gcd(x^2, y^3)$ when $\gcd(x,y)=6$

Let $x$ and $y$ be positive integers and let $\gcd(x,y)=6$. How do we find all the values for $\gcd(x^2,y^3)$? How can we show that these are the only possibilities?
2
votes
1answer
108 views

Simple Answer to Showing $N_{k/\mathbb{Q}}(\alpha)=N((\alpha))$

So I'm trying to show that if we have some number field $k/\mathbb{Q}$ and ring of integers $R_k\subset k$, and an element of $R_k$, say $\alpha$, that the field norm of $\alpha$ is equal to the ...
8
votes
1answer
488 views

Can $x^{n}-1$ be prime if $x$ is not a power of $2$ and $n$ is odd?

Are there any solutions to $x^{n}-1=p$ with p prime, integers $x,n>1$ and $x$ not a power of $2$? $x$ must be even. $n$ is odd since if $n=2m$ then $p=x^{n}-1=(x^{m}+1)(x^{m}-1)$ hence $p=x^{m}+1$ ...
3
votes
3answers
316 views

What's the remainder modulo 7 of the largest divisor of 1001001001 not exceeding 10000?

Let $D$ be the largest divisor of $1001001001$ that does not exceed $10000$. Find the remainder when $D$ is divided by $7$. Let $S = \{2006, 2007, 2008, \ldots, 4012 \}$. Let $K$ denotes the ...
4
votes
1answer
385 views

One sum of squares and two Diophantine equations

This question comes from trying to see why 24 is the only non-trivial value of $n$ for which $$1^2+2^2+3^2+\cdots+n^2$$ is a perfect square. To this end, let $m,n \in \mathbb N$ be such that ...
0
votes
1answer
200 views

Finding the smallest base

$(2)(4)_b$ represents a number written in base $b$. For example $21_3 = 7$. How to find the smallest $b$ such that $(17)(3)_b$ is a multiple of $7$? Assuming,$(17)$ as the single digit,I ...
0
votes
1answer
141 views

Divisibility question

Let $r$ be an integer greater than $2$. Is there a simple way of showing that $2^r$ divides $\left(\begin{array}{c} {2}^{r-2} \\ k \end{array}\right) 2^{2k}$ but it does not divide ...
2
votes
3answers
164 views

When is induction needed?

What is a theorem about the positive integers that cannot (or is not known to) be proved without induction over the positive integers?
4
votes
4answers
119 views

Proof: $2x \bmod 3 \neq 0$ if $x \bmod 3 \neq 0$

I'm not very fluent in mathematical proofs. High School has, sadly, not taught me any kind of proof-theory. That's why I would like your help with my proof of $$2x \bmod 3 \neq 0$$ given that $$x ...
1
vote
1answer
209 views

minimise no. of resistors in circuit

A circuit contains a 1V cell and some identical 1 ohm resistors. A voltage of a/b, where $a\leq b$, is to be made across a voltmeter using the minimum number of resistors in the circuit. The voltage ...
0
votes
2answers
186 views

Proof regarding Squarefree numbers

Prove or find the number of squarefree number is less than $201$. Squarefree: If a number is not divisible by the square of any positive integer, it is squarefree. For example, $21 = 3 \cdot 7$ is a ...
4
votes
3answers
2k views

A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and $8$ respectively

A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and $8$ respectively. The answer is $881$, but how? Any clue about how this is solved?
2
votes
0answers
55 views

roots of unity with LCM [duplicate]

Possible Duplicate: GCD and roots of unity If we have some roots of unity $\zeta$ and $\rho$, in which $o(\zeta)=a$ and $o(\rho)=b$, can we prove that ...
1
vote
0answers
87 views

Tricky GCD problem-Can we prove it? [duplicate]

Possible Duplicate: Is this GCD statement true? Suppose we have integers $h$, $i$, $j$, and $k$. Can we always say that $$ \gcd(h,i) \cdot \gcd(j,k) \,| \, \gcd(hj,ik) \ ?$$ If so, how can ...
2
votes
0answers
165 views

Working with least absolute remainders in the Euclidean Algorithm (possible typo)

I'm reading Burton's Elementary Number Theory (4th edition). On page 29, we read, "The number of steps in the Euclidean Algorithm usually can be reduced by selecting remainders $|r_{k+1}|<r_k/2$." ...