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

learn more… | top users | synonyms

1
vote
0answers
47 views

Egyptian expansion of $x$ [duplicate]

Possible Duplicate: Prove any rational can be expressed as $\sum\limits_{k=1}^n{\frac{1}{a_k}}$ Let $x$ be a number between $0$ and $1$. Let $a_1$ be the smallest positive integer such ...
1
vote
1answer
99 views

Proof of the BOOK: Bertrand's Postulate, $\prod_{p \leq {2m+1}} p=\left(\prod_{p \leq m+1} p\right)\left(\prod_{{m+1}< p \leq 2m+1} p\right)$

I have a question concerning Bertrand's postulate in "Proofs from the BOOK", on page 8: $$\prod_{p \leq {2m+1}} p=\left(\prod_{p \leq m+1} p \right)\left( \prod_{{m+1} <p \leq 2m+1} p\right)$$ ...
5
votes
2answers
308 views

Nice formula for $\sum\limits_{d|n}(-1)^{n/d}\Phi(d)$?

How do I evaluate $$\sum_{d|n}(-1)^{n/d}\Phi(d)?$$ $\Phi(d)$ is Euler's totient function. Thanks.
2
votes
0answers
367 views

Is this sum equal to the Möbius function?

In the wikipedia page Uses of trigonometry under the section Number theory and in the page for the Möbius function there is an explanation for how to calculate the Möbius function from the GCD=1 ...
1
vote
3answers
107 views

Problem about $[x]$

$$[x]-2[x/2]\leq 1$$ Equivalently, $[x]-2[x/2]$ assumes only the values 0 and 1. It seems easy, but I don't know how to prove it...
9
votes
2answers
241 views

An interesting way of producing positive integers

If we define $$\cal N _1 := \{ 1\} $$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ it's easy to prove that, for every $m ...
1
vote
1answer
91 views

How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$?

How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$? If we have canonical representations of $p= q_1^{b_1} \cdots q_n^{b_n}$ and $a= r_1^{c_1} \cdots r_k^{c_k}$, then because $p \nmid a$, $q_i \neq ...
2
votes
2answers
85 views

Finding a solution of $x^{2}=a \pmod p$

Let $p$ be a prime which is $5 \pmod {8}$. Let $r$ be an element of $\mathbb{Z}/p\mathbb{Z}^*$ of order $4$ and let $a$ be a quadratic residue modulo $p$. Prove that a solution of $x^{2}=a \pmod p$ is ...
1
vote
1answer
297 views

The coin change problem in the quantitative way

Today,I came across this problem: Suppose you have a currency, named miso, in three denominations, $1, 10$ and $50$. In how many ways can $107$ miso be given in this currency if you have ...
2
votes
1answer
584 views

How do I prove $n$ is a Carmichael number?

I am having some trouble with this proof and I need some help heading down the right direction: Suppose $n = p_1p_2 \cdots p_k$ where $p_i$ are distinct primes and that $p_i - 1 \mid n - 1$. Show ...
3
votes
1answer
195 views

solving congruence 12x^2 + 28x + 1 mod 35

How do I solve 12x^2 + 28x + 1 mod 35? I tried breaking it into mod 7 and mod 5 but not sure how to proceed from there. Below is my sketch work: $12x^2 + 28x + 1 \equiv 0 \mod 35$ $12x^2 + 7x + 1 ...
1
vote
1answer
101 views

Relations between coefficient and exponent of Proth prime form $k\cdot 2^n+1$?

Definition: Proth number is a number of the form : $$k\cdot 2^n+1$$ where $k$ is an odd positive integer and $n$ is a positive integer such that : $2^n>k$ My question : If Proth number is prime ...
0
votes
1answer
138 views

Integer polynomials with $p$ dividing $f(p)$

If $f \in \mathbb{Z}[x]$ is such that $p \mid f(p)$ for all primes $p$, then $x \mid f(x)$ in $\mathbb{Z}[x]$. This follows by writing $f(x) = \sum \limits_{i=0}^d c_i x^i$ and noting that $c_0 \equiv ...
1
vote
1answer
61 views

Form a compositional identity function

If we have two functions, $f:\mathbb{Z}\rightarrow\mathbb{Z}$ and $g:\mathbb{Z}\rightarrow\mathbb{Z}$ where $g(f(a))=a$ for every integer $a$, how do we satisfy these conditions so that $f$ and $g$ ...
5
votes
2answers
171 views

A continued fraction involving composite numbers

What is the limit of the continued fraction whose partial denominators are the composites?
1
vote
1answer
93 views

How is this not an equivalence relation?

If we have a relation $\sim$ on $\mathbb{Z}/6\mathbb{Z}\times (\mathbb{Z}/6\mathbb{Z}\setminus\{0\})$ so that $(w,x)\sim(y,z)$ if $wz=xy$, how is $\sim$ not an equivalence relation?
0
votes
2answers
238 views

Reverse a mathematics calculation

I have a formula to do the calculation from 7 set of numbers to 4 digits, for example: 04, 05, 19, 21, 22, 31, 13 ====> 4382 These 7 sets of numbers are ranging from 01 to 45, each set will only ...
3
votes
1answer
56 views

How can I show that if $\gcd(a, 3) = 1$, then $a^{560} = 1 \pmod 3$?

I need help getting started on a longer proof and this is the first part: Show that if $\gcd(a, 3) = 1$, then $a^{560} = 1 \pmod 3$ Then we show the same thing with $11, 17, 561$. I have a feeling ...
3
votes
2answers
227 views

If $a^n+n^{a}$ is prime number and $a=3k-1$ then $n\equiv 0\pmod 3$?

Is it true that : If $a^n+n^{a}$ is prime number and $a=3k-1$ then $n\equiv 0\pmod 3$ where $a>1,n>1 ; a,n,k \in \mathbb{Z^+}$ I have checked statement for many pairs $(a,n)$ and it ...
0
votes
0answers
694 views

how to use euler's theorem [duplicate]

If we have $a$ and $p$ where $p$ is prime, how do we use Euler's Theorem to calculate $a\pmod{p}$ when $a$ is a very large number? Any numerical example (for instance, $10^{300}\pmod{13}$) would help. ...
2
votes
2answers
150 views

an invertible element $i$ in $\mathbb Z_n$ must be coprime to $n$

Let $n$ be an integer and $i\in \{1,\cdots,n-1\}$. I want to show that $i$ is invertible in $\mathbb Z_n$ if and only if $i$ is coprime to $n$. One way is easy. suppose $i$ is coprime to $n$ then ...
1
vote
2answers
126 views

Is there an easy way to determine when this fractional expression is an integer?

For $x,y\in \mathbb{Z}^+,$ when is the following expression an integer? $$z=\frac{(1-x)-(1+x)y}{(1+x)+(1-x)y}$$ The associated Diophantine equation is symmetric in $x, y, z$, but I couldn't do ...
1
vote
1answer
196 views

Multiplicative inverse trouble in RSA Wikipedia entry

I'm having a bit of trouble working through an example in the RSA entry on Wikipedia. At step 5, $d$ is calculated as $2753$. However, $d$, which is the multiplicative inverse of $e$, can be ...
2
votes
1answer
432 views

Convergent of continued fractions the best rational approximation of a number? [duplicate]

Possible Duplicate: A nicer proof of Lagrange's 'best approximations' law? I was reading through the wikipedia article on continued fractions, and they state, essentially, that ...
3
votes
4answers
257 views

If $m^3 = n^2$ and $n$ is even, then n is divisible by $4$.

Conjecture: If $m^3 = n^2$ and $n$ is even, then n is divisible by $4$. The proof falls apart from the beginning. $n$ is even therefore there is a number $k$ such that $n=2k$ $m^3 = n^2$ $m^3 = ...
3
votes
1answer
331 views

Divisibility by 4

I was asked to find divisibility tests for 2,3, and 4. I could do this for 2 and 3, but for 4. I could come only as far as: let $a_na_{n-1}\cdots a_1a_0$ be the $n$ digit number. Now from the ...
2
votes
2answers
61 views

if $ax|n$ and $ax+1$ is prime does $ax+1|a^{n}-1$?

Are there any $a,x,n$ such that $ax|n$ and $ax+1$ is prime but $a^{n}-1$ is not a multiple of $ax+1$, apart from $a=x=n=1$? I had an answer to a related question earlier: Can $x^{n}-1$ be prime if ...
3
votes
3answers
166 views

Multiples of a number permute the digits; find such a number

There is a $n$ digit number $N$ with all distinct digits and none of them being $0$. If we multiply $N$ by $1,2,3,4 \cdots n$, we get a number which has a permutation of the digits of $N$. But if ...
3
votes
1answer
149 views

How to find such $a$ that $x^2+ax+a$ is composite for all $x$?

In my previous questions it is shown that $f(x)=x^2+ax+a$ , where $a\in\mathbf{Z^+}$\ $\left \{ 4 \right \}$ is irreducible and that gcd$(f(1),f(2),f(3).....)=1$ So, according to Bunyakovsky ...
2
votes
1answer
144 views

What does the graph of the height function on $\mathbf{Q}$ look like

This question is a bit vague. I was just wondering what the graph of the height function on $\mathbf{Q}$ would look like. Define the height $h(q)$ of a rational number $q$ as follows. Write $q=a/b$, ...
10
votes
4answers
957 views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
4
votes
1answer
324 views

Finding pairs of integers such that $x^2+3y$ and $y^2+3x$ are both perfect squares

Can we find pairs $(x,y)$ of positive integers such that $x^2+3y$ and $y^2+3x$ are simultaneously perfect squares? Thanks a lot in advance. My progress is minimal.
0
votes
2answers
68 views

$\gcd(P(a),Q(a),R(a),S(a),T(a))=1$ for any particular value of $a$?

Let's define five binomials as : $P(a)=2a+1$ $Q(a)=3a+4$ $R(a)=4a+9$ $S(a)=5a+16$ $T(a)=6a+25$ How to prove that : $\gcd(P(a),Q(a),R(a),S(a),T(a))=1$ for any particular value of $a$ , ...
-3
votes
1answer
102 views

A congruence problem

Prove that if $\gcd(a,b)=d$ and $d$ divides $f$, then there is a an integer $k$ such that $a\cdot k \equiv f\pmod b$.
0
votes
2answers
89 views

Sum of $2$ two-digits numbers

$X$ and $Y$ are two-digit numbers. If $Y=2X+2$ and $Y=2X$ in decimal and octal system respectively, and unit digits of $X$ and $Y$ are $5$ and $2$ respectively, then how to find $X+Y$ in ...
5
votes
6answers
998 views

Solutions to Linear Diophantine equation $15x+21y=261$

Question How many positive solutions are there to $15x+21y=261$? What I got so far $\gcd(15,21) = 3$ and $3|261$ So we can divide through by the gcd and get: $5x+7y=87$ And I'm not really ...
6
votes
2answers
477 views

Proving there are infinitely many pairs of square-full consecutive integers

So the question goes like this : A positive integer $n$ is called square-full if for every prime $p$, $p \, | \, n$ implies $p^2 \, | \, n$, i.e. every prime power factor of $n$ occurs at least at ...
2
votes
2answers
1k views

Computing Non-zero End Digits of Large Factorials

Any large factorial will have a number of zero behind it, and one could write an expression to compute the number of trailing zeros, but how would one go about computing the non-zero end digits? E.g. ...
1
vote
1answer
363 views

Proving a Diophantine equation has no solutions

I'm trying to show that $7u^2=x^2+y^2+z^2$ has no solutions in $\mathbb{Z}$ when $u$ is odd. If $u$ is even, then it's simple to show that no solutions exists by looking modulo $4$. The odd case looks ...
2
votes
1answer
961 views

How many ways a composite number can be resolved into two factors which are prime to each other?

Let N denote the number, and suppose $N=a^p \times b^q \times c^r \cdots$, where $a,b,c,\cdots$, are different prime numbers and $p,q,r,\cdots$ are positive integers.Then it is clear that each term of ...
6
votes
2answers
153 views

square squares with diagonals also squares

The numbers reading across and down in these squares are square: $\begin{array}{ccc} 1 & 4 & 4\\ 4 &8&4\\ 4&4&1 \end{array}$ $\begin{array}{ccc} 5&2&9\\ ...
4
votes
1answer
236 views

A number is square in F_p for every prime p [duplicate]

Possible Duplicate: Proving that an integer is the $n$ th power Let $n$ be a natural number, if $n$ is a square in $\mathbb{F}_p$ for every prime $p$, is $n$ also a square in $\mathbb{Z}$ ? ...
0
votes
1answer
194 views

reliable formulas/algorythms to find approximate number of primes up to a value and fast deterministic ways to check if a number is prime

I'm new to this place and I have two problems. I'm writing a program and I need to know: (A) A formula/algorithm for the approximate number of prime numbers up to a number. Example: let's say that I ...
1
vote
3answers
135 views

Does method exist to solve Diophantine/Algebraic equation with nearest integer variable?

Can anyone kindly tell me if there is a method (other than trial and error) to solve equations of the form below: $$x^2 + x - 35 - 35[(x^2)/35] = 0$$ where $x$ is an integer and $[y]$ denotes the ...
0
votes
1answer
350 views

Getting primitive roots of 14

Getting primitive roots of 14. For example, if n = 14 then the elements of Zn× are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. The order of 1 is 1, the orders of 3 ...
7
votes
3answers
477 views

How could we find the largest number in the sequence $ \sqrt{50},2\sqrt{49},3\sqrt{48},\cdots 49\sqrt{2},50$?

How to find the largest number in the sequence$$ \sqrt{50},2\sqrt{49},3\sqrt{48},\cdots 49\sqrt{2},50$$ I am interested in a "calculus-free" approach. Thanks,
1
vote
0answers
72 views

When is a polynomial zero mod $p^{e+1}$?

I am reading the following paper: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4233 It comes to the following claim: If $p$ is a prime number, and $Z$ is a multivariate polynomial, ...
2
votes
0answers
72 views

Prime numbers of the form: $k\cdot 2^n \pm 1$ , where $k<3n$

Is it true that : For every $n$ there exists a number $k<3n$ such that: $k\cdot 2^n-1$ or $k\cdot 2^n+1$ is prime,where $k,n\in \mathbf{N}$ Maple code that prints least $k$ such that ...
6
votes
4answers
391 views

Smallest integer divisible by all up to $n$

What's the smallest integer which is divisible by all integers $1, 2, \dots, n$? Is there a simple way to represent the answer? Call it $f(n)$ here. Clearly factorial ($n!$) satisfies the condition ...
2
votes
4answers
550 views

Is the author Hofstadter cheating in his argument on completeness appling Cantor's Diagonal Proof to Gödel's (natural number) Numbering?

Hofstadter in his book Gödel, Escher, Bach is describing Godel's contradiction of sufficiently powerful versus complete. In the chapter 13 BlooP, FlooP, and GlooP he writes, Now although ...