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

learn more… | top users | synonyms

3
votes
2answers
141 views

last digit of $n^5$ and $n$ is the same digit [duplicate]

Possible Duplicate: The last digit of $n^5-n$ Why is the last digit of $n^5$ equal to the last digit of $n$? Basically, this is the same question as Why is the last digit of $n^5$ equal ...
2
votes
2answers
388 views

If $n$ is composite, so is $2^n-1$ [duplicate]

Possible Duplicate: Simple Mersenne prime divisibility proofs I'm taking elementary number theory and there is this one question that I don't know where to start at... Please help me, ...
2
votes
2answers
399 views

Show $[(p-1)!]^{p^{n-1}} \equiv -1 $ (mod $p^n$) for n $\in \mathbb N$

Show $[(p-1)!]^{p^{n-1}} \equiv -1 $ (mod $p^n$) for n $\in \mathbb N$, by induction. p a prime and p>2. I can't seem to prove the inductive step for this. Would appreciate help. My approach has ...
3
votes
1answer
2k views

RSA solving for $p$ and $q$ knowing $\phi(pq)$

I am trying to find primes $p$ and $q$ in the RSA algorithm given $n = pq$ and the value of $\phi(n)$. I know the following: $\phi(n) = (p-1)(q-1) = pq - p - q + 1$ Solving for $p+q = pq - \phi(n) + ...
3
votes
0answers
1k views

How many different ways are there to get the same product from a sequence of integers?

Let's say we have a list of integers from 0 to (n-1), where n > 0: 0, 1, 2, 3, 4, ..., ...
1
vote
4answers
940 views

Chinese Remainder Theorem and linear congruences

I have found the following congruences: $x \equiv 2\mod 5$ $x \equiv 12\mod27$ $x \equiv 2\mod4$ How can I solve for x using the Chinese Remainder Theorem? Please include justifications for the ...
1
vote
2answers
349 views

Fast Euler's Phi function and linear congruence

I am trying to solve $5k \equiv 2\mod7$ with Euler's phi function. $5$ and $7$ are relatively prime so we can write: $5^{\phi(7)} \equiv 1\mod7$. Multiply by $5^{-1}$: $5^{\phi(7)-1} \equiv ...
1
vote
2answers
248 views

solving and manipulating linear congruences

I need to find a multiple of $5$ call it $5k$ with the following properties: $5k \equiv 3 $ mod $6$ $5k \equiv 2 $ mod $7$ My first instinct is to start with the Chinese Remainder Theorem, but I ...
4
votes
1answer
64 views

A harder tournament to schedule

Let us suppose that I have $n$ students in my class, and I break them up into $k$ groups per week. Let's also suppose that I want to repeat this each week, except that I don't want any student to ...
1
vote
1answer
90 views

Mathematical model for truncation of digits.

I wanted to find a mathematical expression to represent the truncation of the least $D$ digits of a number with radix $r$ without using the "floor" operation. So a $Q$-digit number written as ...
1
vote
3answers
112 views

Given RSA encoding function $E: x\to x^7 \pmod{6161} $ find decoding function D

So far I got: $7\alpha \equiv 1$ mod $\phi(6161)$ $\phi(6161) = \phi(61) \times \phi(101) = 6000$ $7\alpha \equiv 1$(mod $6000)$ At this point we are supposed to do euclid's algorithm and somehow ...
2
votes
1answer
737 views

What is the remainder when $4^{100}$ is divided by 6?

I am trying to find the remainder when $4^{96}$ is divided by 6. SO using the cyclicity method, Dividing $4^1$ by 6 gives remainder 4. Dividing $4^2$ by 6 gives remainder 4. Dividing $4^3$ by 6 ...
1
vote
5answers
303 views

Find the missing digit in a multiple of 48

The question I'm working on is as follows: "In $62894\_52$, the hundreds place digit is missing. If $48 \mid 62894\_52$, find the missing digit." I'm not really sure how to solve a problem like ...
3
votes
2answers
169 views

Is the amount of change in my pocket bounded?

Suppose I always pay for things with exact change, if I have it, or the least amount over the cost of the item(s) if I don't have exact change (in which case I'll get change from the seller). Also, ...
3
votes
4answers
76 views

$Y^3$ congruent to $1 \pmod {p}$

How to get the condition on $p$ for which $y^3$ congruent to $1$ modulo $p$ has $3$ solutions ( $1$ solution $x= 1$ is always possible, right ?).
2
votes
3answers
311 views

Least Common Multiple of Fractions

how do i find lcm of two fractions? For example: $\frac{2}{3}$ and $\frac{5}{8}$
9
votes
3answers
334 views

Writing 28913000 as the sum of two squares

A little number theory fun. I am given that $167^2 + 32^2 = 28913$, and I am asked to find integers $a$ and $b$, such that $a^2 + b^2 = 28913000$. Here's my thought process so far: Knowing that ...
1
vote
1answer
134 views

How to solve for the $n$-th Fibonacci number that is greater than or equal to $N$?

The general formula for the $n$-th Fibonacci number is: $$\frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}$$ where $$\phi = \frac{1 + \sqrt{5}}{2}$$ Given $N$, is there a way to solve for $n$ in this ...
-1
votes
2answers
96 views

Does the sum of the digits tell us anything about the relation between these two functions

The number $K$ is expressible as part of one of either of two quadratic functions with integer coefficients. One of the functions is quadratic in $\pi$ and one is quadratic in $e$: ...
1
vote
1answer
66 views

How to get the result using Pepin's test

How do I achieve this result via Pepin's test by using Euler's Theorem and such to simplify $3^{2^{31}}$ and get the desired congruence of 10,324,303? $3^{(F_5-1)/2} = 3^{2^{31}} = 3^{2,146,483,648} ...
5
votes
2answers
724 views

Find all positive integers $n$ such that $n$ is divisible by all the positive integers less than or equal to $\sqrt{n}$

Find all positive integers $n$ such that $n$ is divisible by all the positive integers less than or equal to $\sqrt{n}$ My thought: If n is a positive integer, let d(n) denote the number of positive ...
6
votes
8answers
3k views

Proof problem: Show that $n^2-1$ is divisible by $8$, if $n$ is an odd positive integer.

Show that $n^2-1$ is divisible by $8$, if $n$ is an odd positive Integer. Please help me to prove that whether this statement is true or false.
1
vote
4answers
266 views

Elementary Number Theory. Test Question.

If $a,b$ greater than or equal to 1 and if the $\text{gcd}(a,b)=1$ explain how we know that the $\text{lcm}(a,b)=ab$.
1
vote
1answer
129 views

Diophantine congruence equation

Prove the equation $$x^2+17y^2 \equiv 257 \pmod p$$ has integer solutions modulo $p$ for every prime $p$. Note: The case $p=2$ is trivial. If $p$ is odd and $p \nmid 257-17y^2$ I tried to consider ...
4
votes
1answer
247 views

gcd and fermat's little theorem

I know the following: gcd($b$, $561$) = $1$ How can I show that $b^{560}$ $\equiv$ $1$ mod $3$ ? I see that $561$ is not prime as $561$ = $3*11*17$. My first thoughts are: gcd($b$, $3$) = $1$ so I ...
1
vote
2answers
1k views

Find all integer solution of the equations:

Find all integer solutions of the equations: \begin{cases} 6x+21y&=&33 \\ 14x-49y&=&13 \end{cases} I'm not sure how to find all integer solutions for a, but I know there are no ...
0
votes
4answers
1k views

Prove that if c is a common divisor of a and b then c divides the gcd of a and b..

If $c$ is a common divisor of $a$ and $b$ then $c$ divides the greatest common divisor of $a$ and $b$. What can we use to prove this?
1
vote
3answers
453 views

Elementary number theory, if a divides b show that..

If $a$ divides $b$ argue that $a^3$ divides $b^5c$ for any $c$.
0
votes
2answers
101 views

Elementary Number Theory.. If a divides..

If $a \mid (2c+3d)$ and if $-a \mid (c+d)$ then show that $3a \mid 3c$. The only progress I can say I've made is that the question is basically asking to show that $a \mid c$, because the $3$ is only ...
1
vote
1answer
53 views

Inequality with numbers

It seems its a simple question, but I am confused. Let a be natural number and let b be some number $1\le b\le a$. Find an upper bound for $$ \frac{a^2+2b^2-4ab-a}{a(a-1)}. $$ I've got $$ ...
5
votes
0answers
85 views

Integer weights used to cover all numbers from 1 to N with redundancies in case of breakage

Bachet's Problem (arxiv) is a famous problem where we have to find the smallest set of positive integers such that they measure every number between 1 and 40. This can be generalized to every integer ...
3
votes
3answers
370 views

Characterising reals with terminating decimal expansions

Show that a number has a terminating decimal expansion if and only if, it is rational and when in lowest terms, its denominator is coprime to all primes other than $2$ and $5$. This is an unsolved ...
4
votes
1answer
1k views

How did Euclid prove Euclid's Lemma

In Elements, Book VII, Proposition 7, Euclid states: If a number is that part of a number which a subtracted number is of a subtracted number, then the remainder is also the same part of the remainder ...
6
votes
2answers
3k views

Every natural number can be written as the sum of distinct Fibonacci numbers?

Can anyone hint me to prove: $\forall n\in \mathbb{N}: \exists$ Fibonacci numbers $ F_{i_1},\ldots,F_{i_k}$ such that: $$\sum F_{i_k}=n$$ Note: Every Fibonacci number can appear only once. Thanks
-1
votes
2answers
53 views

Determining when an inequality holds

Suppose I have $0 < N - \varepsilon < q$ where $N$ is some large real number and $\varepsilon$ is much smaller than $N$. Can I conclude that $0 < N - \varepsilon < N < q$?
1
vote
1answer
152 views

Perfect squares

Wonder whether anybody here can provide me with a hint for this one. Is $c=1$ the only case in which the expression $(c^2+c-1)(c^2-3(c-1))$ returns a perfect square?
0
votes
1answer
69 views

Any interesting number-theoretic results/properties concerning particularly values of $n$ in $2n+1$? [closed]

So this question has strange origins: I was looking at the Leibniz series for $\pi$, and I started to wonder about the relationship between the partial sum and the parity of the value $n$ in the ...
4
votes
2answers
613 views

Problem about $n$ six-sided dice and the sum of the values

(AHSME 1994) When $n$ standard six-sided dice are rolled, the probability of obtaining a sum of 1994 is greater than zero and is the same as the probability of obtaining a sum of $S$. What is the ...
1
vote
0answers
65 views

Relation between b and c such that $ b^2 + c^2 + b^2 c^2$ is a perfect square [duplicate]

Possible Duplicate: On the equation $(a^2+1)(b^2+1)=c^2+1$ I came across a problem: What is relation between $b$ and $c$ such that $b^2 + c^2 + b^2 c^2$ is a perfect square? After trying ...
0
votes
2answers
147 views

Operations on Congruences

What operations can I perform on congruences to transform the modulo n? Specifically, in a formula such as Fermat's Little Theorem (or a generalization) $b^{p-1}$ $\equiv$ $1$ mod $p$ What ...
2
votes
1answer
36 views

expressing the gcd(n, m) = 2

What are alternative ways to write gcd($n$, $8$) = $2$ ?? This is part of larger proof. I do not see writing the gcd as a linear combination as much help: $2$ = $nr$ + $8s$ Ultimately, I am trying to ...
0
votes
1answer
200 views

Simple modulus algebra - rabin karp weird implementation

I'm studying the Rabin Karp algorithm and something isn't clear about the modulus algebra: Let's suppose I have all base-10 numbers for simplicity's sake $14159 = (31415 - 3 \cdot 10^4) \cdot 10 + ...
4
votes
4answers
1k views

Working with Clocks

I have frequently seen problems like how many times between _ and _ will the minute and hour hand be together, or be 90 degrees apart. So if someone can give me a complete solution to the following ...
0
votes
2answers
149 views

The discriminant of an integral binary quadratic form and the discriminant of a quadratic number field

Let $ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. Let $D = b^2 - 4ac$ be its discriminant. It is easy to see that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Conversely ...
1
vote
1answer
67 views

Summation of Modulo Sequences

I came across through simulation that multiplying and adding certain modulo sequences yield equal results. Consider the following two sequences \begin{align} g_0[k] &= \sum_{n=0}^{N-1} \left< ...
2
votes
1answer
130 views

Equivalence classes on Z

So I'm given that R is an equivalence relation on Z, and that adding classes in the natural way is well defined. That is, class(a)+class(b) = class(a + b). I want to show that R can only be equality ...
3
votes
0answers
471 views

Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
0
votes
2answers
121 views

How many multiples of two primes equal eachother

Given two distinct primes, $p_1,p_2$, is it true that there are no non-zero integers $k_1,k_2$,$|k_1| < p_2$, $|k_2|<p_1$ such as that: $$k_1p_1=k_2p_2$$ If so, how to prove it?
1
vote
1answer
115 views

Power Variant of Fibonacci sequence

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like ...
14
votes
4answers
2k views

Proving that there are infinitely many primes with remainder of 2 when divided by 3

I need to prove that there are infinitely many primes with remainder of 2 when divided by 3. I started out similarly to Euclid's classic proof of an infinite number of prime numbers: Suppose there is ...